"piece of cloth used to mend another material," late 14c., pacche, of obscure origin, perhaps a variant of pece, pieche, from Old North French pieche (see piece (n.)), or from an unrecorded Old English word (Old English had claðflyhte for "a patch").
Meaning "portion of any surface different from what is around it" is from 1590s. That of "small piece of ground," especially one under cultivation, is from 1570s. As "small piece of plaster used on the face," to cover blemishes or enhance beauty is from 1590s. Phrase not a patch on "nowhere near as good as" is from 1860.