You'd have to get quite a bit further west (Greenland) to get in the prevailing currents to end up in Nova Scotia.
Looking a current map.
Obviously it would have been easier to travel via the North Equatorial Current. This is what Columbus did, no doubt earlier man did it too. Easy to travel up rivers along the Gulf Coast and end up in all kinds of places. Or get blown to the East Coast of Florida and travel up to the Carolinas and Virginia.
Between 19,000 and 13,000 years ago the great ice sheets made the North Atlantic currents far, far different from today. For example, pollen deposits in North Africa showed that the Gulf Stream flowed there, rather than Northwestern Europe. Due to the lowered sea levels, the continuental shelves of both North America, Europe and Africa were land. The Grand Banks off of Canada would have been dry land, four times the size of today's Newfoundland.
The winter ice shelf/ice pack line would have extended from this Grand Banks land to Iberia with only 1500 miles of ocean to travel. Hunters preying on seals and other aquuatic species could have easily beached on ice floes or shelves while persuing game.
Perhaps some of them made it to the Grand Banks. Travelling further westward, they would have encountered more ice, which was not strange to them at all. Eventually, they would have reached continental North America. A turn southward (perhaps looking for harborage during a storm) would have led them to the Virginia/Carolina beaches, ice free during the ice ages.