What we think of today as wine is not of the same alcoholic percentage as several millennia ago. For example, the main difference between Roman and modern wines was likely their alcohol content, as both Greek and Roman wines likely had as high as 15% or 20% ABV, compared with 10-12% or so in most modern wines. From Greek literature, we know that wine was almost always diluted, usually with water (or snow when the wine was to be served cold). The Greeks believed that only barbarians drank unmixed or undiluted wine and that the Spartan king Cleomenes I was once driven insane after drinking wine this way.
Deuteronomy was probably composed during the Babylonian captivity (597-539 BCE) or during the Persian period (539-332 BCE). Between that period and Alexander the Great (356 BCE) is not really a "long time" in the first case, and even overlaps in the second case. Even before that, trade between all Mediterranean regions in the bronze age (up to around 1500 BCE) was common.
Around 1550 BCE Palestine was conquered by Egypt for several hundred years. Wine in Ancient Egypt has been documented as far back as the 3rd millenium BCE. The industry was most likely the result of trade between Egypt and Canaan during the early Bronze Age, commencing from at least the 27th-century BC Third Dynasty, the beginning of the Old Kingdom period. Winemaking scenes on tomb walls, and the offering lists that accompanied them, included wine that was definitely produced in the delta vineyards. Records from the early dynasties importing wine from the Levant have been found.
Furthermore, the Hebrew text of Deuteronomy 14:26 does not make a distinction between wine and "strong drinks" other than the source of wine being grapes. It has no "special" reference to a different level of intoxication:
shecar (שֵׁכַר) means "Any drink which can inebriate, whether that is made from grain, or the juice of apples, or when honey is boiled into a sweet and barbarous potion, or the fruit of the palm [dates], is expressed into liquor, and the duller water is colored by the prepared fruits".
In modern Hebrew, we still find this word as an adjective for "drunkard": shikkor. The source of intoxication to describe the state is irrelevant.