with Eden (and East) at the top
It certainly wasn't in Europe, which was fairly well traveled, and so the medieval mind had to look beyond the lands they knew. The 13th century Hereford map (a mappa mundi of the T-O pattern; see the link above) places Eden on an island near India, surrounded by not only water but also a massive wall. Ralph Higden places it not only in the less-understood-to-Europeans Asia, but makes clear it is an inaccessible part of Asia (you have to explain why no one has stumbled upon it and returned with the news).
Hrabanus Maurus was a little more cautious:
Many folk want to make out that the site of Paradise is in the east of the earth, though cut off by the longest intervening space of ocean or earth from all regions which man now inhabits. Consequently, the waters of the Deluge, which covered the highest points of the surface of our orb, were unable to reach it. However, whether it be there, or whether it be anywhere else, God knows; but that there was such a spot once, and that it was on earth, that is certain. [De universo (Concerning the world)]A German priest of the 15th century, Meffreth, seems to be the only person who thinks himself qualified to actually answer the question "Wouldn't Eden have been washed away in Noah's Flood?" He has left us a sermon in which he claims that Eden exists on an extremely tall mountain in Eastern Asia—so tall, that the waters that covered Mt. Ararat merely lapped at the base of Eden on this mountain. He further explains that four rivers pour from Eden at such a height that the roar they make when descending to the lake at the foot of the mountain has rendered the locals completely deaf.
After the 15th century, we find few references to a terrestrial location of Paradise. As man started to circumnavigate the globe and explore the interiors of more continents, it became clear that finding Eden was not going to be a simple matter of traveling.