A West European/West African nation exploring it more circa 1000-1200 is probably the best bet, unless you use butterflies going very far back to bring technological development further ahead.
Those locations are the closest to the Americas, and the ones with the best winds. Chinese explorers, by contrast face a much bigger route: not only is the Pacific bigger, but they would have to go North to the Russian Far East before being able to find favorable winds to Canada. Southeast-Asian Explorers (e.g Phillipines), have an almost impossible task - they would have to cross the Pacific at its widest point without wind power.
1000-1200 is also the Medieval Warm period, when Greenland is Green and the northern seas are free of ice and full of fish. Fishermen and explorers already made it to the Americas in this period OTL, creating some factors that push for greater exploration/settlement is possible. Coincidentally, this is also during the Islamic Golden Age, with strong African Arab states that have advanced astronomy and maritime technology.
Possible POD's: Stronger Viking Kingdoms in Britain/Scandinavia encouraging more exploration, Weaker Vikings, with their absence allowing other Kingdoms (Anglo-Saxons or Normans) to take their role. Stronger Persia/Byzantium managing to threaten Arab trade in the Red Sea (leading them to explore West Africa more), earlier Moor defeat in Spain, leading to a greater focus on the west African coast.
If you want something even earlier, you can have Carthage survive and prosper, a Roman Empire that focuses west instead of east (possibly due to stronger Persia/Greece), a Celtic Empire that grows strong in the absence of Rome, and things like that.