I doesn't really need to be believed, simply be attempted. Knowing Greenland was there was a big deal, but if we presume we've got Iceland-Greenland-Vinland already, there is some value in being able to make the passage from Iceland-Vinland directly. Heck, there is plenty of justification to be interested in making the trip from Britain and Ireland, rather than Iceland at all. (And as mentioned, Vinland was found by accident in exactly the way the OP wants)
So you have a motivation already, proof it can be done, a shorter route, direct, but a single leg. A leg of 3,262 km. Yikes. So we need to have larger craft. Now the Norse have seen bigger ships in their raids in the Med, that construction isn't always good, but the idea of building bigger to make the journey isn't ASB, you just need the motivation.
So lets go for one, a Cnut the Great PoD, or rather his sone, Harthacnut. If he lives rather than has a stroke at a wedding, we have the third successive ruler of the North Sea Empire. As to how united it is, is for debate, but it does have relevance. As a Thallassocracy, it needs many, large ships, and considering the realms tumultuous nature, a place for exile isn't bad, but a place to expand to, establish loyal (if distant) families, to exile disloyal families, and generally provide a place to clean shop, is very useful. The people provide the manpower for Vinland to survive, and the North Sea Empire has the incentive for the ships and shipping that can transport the large quantities of goods with the supplies involved - as they need it in the North Sea for large-volume transport anyway.
So yeah, if you want people to do this, you need the motivation, and the likelihood is that it'll be political rather than purely economic. After conquering the rest of Britain and Ireland, Europe is mostly out of bounds. Sweden is likely, as is the Baltics, but so is Vinland. And as the trip via Greenland becomes more dangerous, being able to sail from further south directly will help them, and allow them to interact with the peoples of North America, and expand the trade network further.