Per the Middle English Dictionary, the answer is 'yes'.
Ye forsaides ... John And Robert schall make a brigge of stane oure ye water of Swalle atte Catrik, be twix ye olde stane brigge and ye Newbrigge of tree, quilke forsaide brygge with ye grace of God sall be mad Sufficiant and workmanly in masoncraft.
(1421) Indent.Catterick in Archaeol.J.7
I'd translate this as
The aforesaid ... John and Robert shall make a bridge of stone over the water of [Swalle] at the Catterick, between the old stone bridge and the new bridge of wood, which aforesaid bridge with the grace of God shall be made sufficient and workmanly in masoncraft.
-so while it's clear that the y in "Ye" is a form of th/thorn, it's also clear that transcribing it as a y is not necessarily a mistake.
The MED entry for shop(pe includes the spelling shoppe as a variant header form. Similarly, the entry for old(e includes the spelling olde as a standard variant, among an astonishing variety of spellings.
Both words have the desired meanings — old "3.(a) Of things: long in existence or in use"; shop "A room or building used as a place of business by a victualer, craftsman, etc."
Thus, although I didn't find the actual phrase "the old shop" (in any spelling) in the quotes, it fully conforms with the usage patterns I can see. I think the spelling "ye olde shoppe" would be unremarkable in a Middle English context.