Coastal foraging? Why can't they just fish? There are lots of fish in those northern reaches today, I assume there would have been even more back then. And fish doesn't necessarily have to be cooked, so no requirement to stop to make fires.
Anyway, the current understanding of the paleoclimate is that entire region between approximately Valdez and Vancouver Island was entirely covered by glaciers out to the edge of continental shelf until ~18kya. Lesnek et al has some good diagrams [1]. Living exclusively off deep-sea marine resources in an iceberge minefield without fire for over a thousand miles in one of the coldest, most dangerous oceans in the world without landing suggests an unprecedented level of both nautical technology and experience. Where did that come from? We have no good answers right now.
The boat would be hauled onto the ice and turned upside down to form a shelter in remote spots.
Fishing and hunting for seals would have provided the food as they went.
See https://en.wikipedia.org/wiki/Genetic_history_of_Indigenous_...
https://www.smithsonianmag.com/science-nature/dna-search-fir...
Additionally, the farthest east that we've found evidence of Australasian populations is the Solomon islands, some 7,000+ mi from South America. There's no evidence of habitation on the intervening islands until Austronesian peoples show up much later. As for Africa, we simply have no evidence for it whatsoever.