Could a sustainable colonial presence be achieved in the Americas earlier?
has a very simple answer. No, not before certain technology is discovered. There are some politics/infrastructure issues at play that drove some of those discoveries, and a certain competitive spirit/desire to exploit new lands first, but technology is KEY.
First piece of the puzzle--a compass. And not just any, a reliable one! I know that seems absurdly simple, but introducing this earlier and in a more widespread manner could help (China was 11th Century).
Here's the interesting thing, China and (the Arab world somewhat) actually had more of the tech needed than any other place, earlier. Like you said, it was only a moratorium on travel that prevented it from happening. But it was still only about 90 years before Chris Columbus did his thing.
Improvements in ship design such as sternpost rudder, multiple masts and lateen sails, which happened later.
Let's take a look at the time from discovery to colonization-- 1492 was Columbus, but true colonization by the Spanish didn't really get into full swing until the 1530s. That's a gap of about 40 years. In those 40 years, explorers mapped as much as they could, and enticed with descriptives of the land, bringing back plants and adventures. News travels more slowly, the further you go back in time...and some of that is dependant on, again technology.
Realistically, you need time for the news to spread in order to get investors and candidates for colonization. Looking at the time frame, there is one thing they had that they hadn't had the century before...the printing press. By the 1600s when England got into the act, printed adverts and handbills were most definitely part of what was needed for the push to colonize.
By changing a few things, such as politics and early tech discovery/spread, you MIGHT be able to push the start by several decades, but I'd say no more than 90 years. This is the sort of thing that has a lot of moving parts, and I would hesitate to say yes to.
Note that colonization is not the same as DISCOVERING or simply spreading a culture. For instance India, which was occupied by people and powers was colonized by the Brits. For Colonizing you need COUNTRIES claiming a territory outside their own. col·o·nize ˈkäləˌnīz/Submit verb gerund or present participle: colonizing (of a country or its citizens) send a group of settlers to (a place) and establish political control over.
The Polynesians set up trade routes but the islands had separate cultures--they weren't sending money back to a mother country or being taxed and having resources. From Wikipedia: "While the early Polynesians were skilled navigators, most evidence indicates that their primary exploratory motivation was to ease the demands of burgeoning populations. Polynesian mythology does not speak of explorers bent on conquest of new territories, but rather of heroic discoverers of new lands for the benefit of those who voyaged with them."
That is markedly DIFFERENT from colonization. Colonization involves exploiting resources not simply for the benefit of those who wish to go and develop a different place. It is for the benefit of the country or power that colonizes.
Having global powers interested in this sort of exploitation, plus tech such as a printing press to spread the word is, I think key to this. You need a lot of replacement settlers to do this because of disease and lack of infrastructure.