Ouch. Would an able-bodied population with all the necessary tools and constant access to Europe be able to reverse the erosion/desertification scenario?
Also, would potatoes make a better crop there as in Ireland?
EDIT: Also, what if instead of sheep they tried to exploit caribou and muskoxen as sources of food?
Poatoes came from the Andes originally. They were acquired by Europeans after Colombus and only adopted in Europe in the 18th century or thereabouts.
Musk Ox, as has been pointed out weren't anywhere near the Norse. The only place they'd be found is in the extreme north of of greenland.
It's very hard to establish a new domesticate. It's a significant effort to domesticate. There's a huge learning curve and an investment curve.
Among other problems that you've got here is that Caribou are incompatible with sheep. Sheep carry KMT (sic), a cervine disease. Harmelss to them but almost instantly fatal to carbou.