I'm a long time lurker which have just becomed a member, I think this idea have some potential.
I think that a colonisation under John of Denmark would be one one of the better choice. It could happen as a reaction to the Treaty of Tordesillas. John had a claim to Greenland and Vinland as king of Norway. So as a reaction he could send expeditions to push his claim. As the find the St Lawrence river, which is a easy access to the continent. John set up some trading post to both push his claim and make a little money. As the local natives begin to die, first his son, later his brother and his brother's descendent being to send fur trappers (mostly Norwegians) and merchants into the continent. Some farms are set up to feed the outposts. While this colony only start with a few people, it increase through natural population increase and by 1600 the colony is home to 5000-10000 Scandinavian colonists, if we see the historial increase of settled European population in Canada and northern USA we will likely see a doubling every 20 years. So this would givbe us between 80000-160000 Dano-Norwegians by 1700.
That seems pretty high. Wasn't the total population of Denmark-Norway (plus Iceland/Faroes) something like 1.2-1.5 million in 1600? That's less than Portugal at 2 million and about a quarter of the British Isles. Now Portugal did have very high rates of emigration proportionately to Brazil, but that was mostly with gold on the line. Here you have decent (at best) farmlands, very, very rich fishing (initial lure, no doubt), and the fur trade. Now, the fur trade as we saw historically is going to enrich the colonists/mother country, but also touch off some nasty wars both against the colonists and between native groups, which touches off more wars everywhere. And god so help if England or France get involved through a New England settlement. Indian Wars could end up killing huge amounts of those people and lay tons of land to waste (see all the examples in New England). Granted, that damage is reparable and survivable, but the amount of emigrants can never be as high from Denmark-Norway (or even a united Kalmar Union state) as it was from England.
There's also an idea with religion. This guy
here is according to some theories King John's son, or if not, from a powerful noble family. So if he gets the ear of the king, maybe he starts evangelising the natives. If he doesn't end up killed in the process, he might find converts and establish a Catholic tradition in some groups. If Denmark-Norway becomes Protestant as in OTL, then suddenly, these priests might not like that, and then you'll end up starting a war with the natives and...issues. That goes even moreso if France gets involved somehow--rival colonisation in the Maritimes, French *New England, I don't know.
But a combination of fur trading, the Grand Banks, backed by a decent amount of people seems solid. I don't know how far they'd get in King John's day, but if you have a small base of Europeans by the 16th century in the Maritimes, then you're probably on the way to something good.