It is possible, but highly unlikely. The big problem is why are the Norse exploring?
For people to spend such a long time travelling, there needs to be a profit motive. They still must earn a living and feed their families. They can't spend precious capital and time on a whim to explore just because.
The Age of Discovery was done because 1) Europeans wanted to find the source of valuable commodities, and 2) despite the huge costs involved, the crowns of Europe were willing to back explorers because of the potential return.
In travelling the North American coast, I don't see what the potential benefit is, and I don't see any fabulously rich patron supporting such a venture.
Look at the comparison between East and West side of Atlantic.
Hugging the coast from Norway through Strait of Gibraltar to Italy, which the Norse DID accomplish by 859 - mere 66 years after Lindisfarne raid - is about the same distance as hugging the coast from Newfoundland through Strait of Florida to Yucatan.
Now, the obstacles are different. The incentives are also different.
A Norse raider following the East coast south past France and Spain was at a big danger, facing formidable perils. Namely, the coast was lined by illwishers. They were numerous, they were armed with iron weapons and warhorses, they were led by lords and kings. And though they might flee the Norse or buy them off, a Norse who let his guard down was in dire peril everywhere - an European lord stood to get renown and praise by surprising and slaughtering any lost or unwary Viking.
There was not much that the Norse might offer that Europeans might want. They could realize their loot in Europe or take employment as mercenaries against local enemies, but this was going to be a bad PR to any fence/employer. They DID eventually find valuable exports - salted cod, the local fishermen did not do equally good job preserving their catch - but this would be sometime in 13th century, and then carried by German ships, not Norse. Honest traders like Ottar did make their way to England, but not to Mediterranean.
The obstacles on the West coast are different. The Skraelings are less numerous, lacking domestic animals and metal tools. They are therefore also less well armed and less organized.
And importantly, the Norse HAVE a valuable trade good to offer. Iron tools.
At best, it is an extremely slow process. Colony in Vinland established. Then as that colony reaches sufficient size, Norse fisherman follow the cod fisheries down the east coast.
They wouldn´t. They would not run out of local cod so soon.
Then something has to prompt them to continue south and west among people even more primitive than they are who don't seem to have anything worth trading. At best, it happens after several decades or centuries of established Norse presence in Vinland.
Obvious trade good is maize. The Norse would certainly grow their own barley, oats and rye in Newfoundland... but they might find it very cost efficient to sail a knarr lightly loaded with small amount of iron tools to Hudson, Delaware or Chesapeake, and return heavily laden with maize. It might turn out to need less labour than growing the same amount of barley in Newfoundland.
Beyond the first maize growers.... Are there any low volume, high value goods (such as labour intensive products) that the Skraelings of Eastern Woodlands cultures would produce and that the Vinland Norse would value?