The article does not actually claim pre-Viking contact.
We already know, from both the Icelandic Sagas and archaeology finds, that around 1000 AD, Vikings settled in Greenland, then tried it again in Newfoundland ("Vinland")(*). This latter expedition first cruised past two other pieces of land, called Helluland and Markland. These two most probably correspond to Baffin Island and Labrador, respectively. An important point is that both Iceland and, even more, Greenland, lacked a good source of wood. Wood was a scarce resource, yet crucial for building houses, ships and tools in Viking society. The coast of Labrador is ripe with trees, and the name "Markland" reflects it (it means "Forest Land"). Therefore it is quite plausible that Vikings from Greenland and possibly Iceland would regularly make the trip to Markland, not to settle but to fell trees.
Indeed an Icelandic document from 1347 reports a ship going off course and landing in Iceland while in the process of returning from Markland (the probable intended destination being Greenland). We know that sagas tend to report only heroic feats, and lumberjacking was probably not heroic enough to warrant its own verse.
If we accept the idea of at least semi-regular trips between Greenland and Labrador, following the navigational course that goes near Baffin Island, then it is highly probable that some parties actually made landfall on Baffin Island at least occasionally, if only in case of bad weather or emergency repairs. The artefacts reported by Sutherland then make a lot of sense. They don't actually imply either a permanent settlement or trade relationships with Inuit people, but they show presence. A settlement would be problematic because Vikings tended to rely on cattle for food, and maintaining cattle on the definitely non-grassy coast of Baffin Island would be very challenging. The Greenland settlements were abandoned in the 15th century, which hints at Vikings unable or unwilling to alter their lifestyle into more "Inuitic" practices. If Vikings stopped on Baffin Island for anything else than immediate survival, then a trading post would be much more plausible than a true settlement.
Yarn and sticks don't unambiguously point to Vikings, as opposed to other European societies of that time; that's what is meant by the expression "or other Europeans". But Vikings were in the vicinity (Greenland, and briefly in Newfoundland), had the seafaring abilities, and the navigational knowledge (the road had been reconnoitred), and the economical motive (wood from Markland). Invoking other people is a bit far-fetched.
To sum up, the archaeological evidence more indicates Viking exploration (or possibly settlement or trade) on Baffin Island than non-Viking or pre-Viking contact. However, it does show that these things were happening relatively early, around 1000 AD, that is right after the first settlement in Greenland, which makes sense since they needed wood from the very beginning.
(*) We are not really sure that Vinland is Newfoundland, though the Anse-aux-Meadows site certainly matches the sagas.