I have no essential disagreement with that. I was not suggesting that it could only begin in the 14-15th C.
"Stoneage" thru late medieval Europeans (or Maghrebis or other Africans) would still need that foundation of adequate technology (the Polynesian voyaging canoe was a marvel of deceptively simple but very effective technology that never really had an analogue among Mediterranean and Atlantic cultures until much, much later -- the Viking knarr maybe being the first Western craft suitable) and the requisite understanding of how the currents and winds of the Atlantic worked, and a navigational system that worked out of sight of land.
Again, the Polynesians were way ahead of the game in this regards in their expansive corner of the World. Truly without peer.
The issue is kickstarting that foundation building plausibly earlier. Motivation is necessary. What gets a culture to start blindly sailing West across a seemingly infinite Atlantic, not knowing if there is anything (not even having rumor or traditions of anything) --- especially anything worthwhile? Especially as there was so much at hand that was tangible via coastal sailing, along the European and African coasts.
OTL, I think the Madeiras were the remotest Atlantic lands ever ventured to by Classical era peoples. Even that must have been an epic accident.
I think you're correct in all particulars. There is some potential for Island hopping for the Macaronesia Island complexes, and truthfully, they were all discovered during the age of exploration. Some of them may have been found in Antiquity, but were judged without value.
For an effective POD, we would need some motivation for either the mediteranean cultures or atlantic cultures to venture out into the Atlantic. What could that be? Possibles:
* FISHING or bulk fishing/deep sea fishing.
The trouble is that fish decompose quickly, unless preservation measures are taken. So you don't want to fish too too far from population centers.... most of which are not close. The other point is that the Mediteranean has plenty of fish.
It seems fairly clear that the Age of exploration was driven in part initially by pursuit of sea harvest, particularly Basque fishermen and whalers, who were travelling to locations as remote as the Grand Banks and Svalbard.
I'm just guessing, but the Norse seafaring tradition might have evolved from the need for coastal fishing to supplement harvests, and possibly to reach otherwise inaccessible fjords.
But from what I can tell, Atlantic sea harvest, for fish at least, doesn't seem sufficient.
* WHALING might do the trick. But you would have to have some sustained cultural priority for a very valuable and very fungible whale product - ambergris, blubber, baleen etc., which doesn't seem to have been there.
When I did my Ice and Mice timeline (apologizing in advance for the self referentiality) I posited the evolution of an Inuit deep sea tradition evolving from coastal whaling in Greenland, that lead to colonizing most of the arctic islands.
But here, while there might be potential, I'm not sure how viable it would be. The Ancient world was crazy for aromatics - myrh was worth more than its weight in gold and frankincense was a number one trade good. So maybe there might be a crazy lucrative market for ambergris or whale (fish?) based aromatics? Possibly enough to sustain continuous economic activity and an evolving ocean tradition? But the aromatics trade was well established and based in and around Somalia/Arabia trade routes. It's quite speculative to suppose that possibly unreliable, unsophisticated traders from the other side of the ancient world might enter that market.
As to other whale products - whale meat? Simply not enough storage or portability for what amounts to a relatively low value, high bulk foodstuff. Possibly you might develop a market for baleen, whalebone, whale ivory or oil or some esoteric product. But it seems farfetched.
* ISLAND HOPPING - So far as anyone knows, nothing valuable enough on the Macaronesian islands was there to encourage a settlement and regular traffic, or consequent leapfrogging, discovery and colonization.
* TRADE TO REMOTE LOCATIONS - Again, there's nothing in place.
Tough one....