Across the ocean? The walking theory breaks down when you look at the development of the Americas. That actually almost certainly kills any theory that communication is required. At least in the Americas, the timing was surely a coincidence?
From what I've heard, transatlantic boats can be fairly small and rudimentary.
Not really. The Vikings pulled it off, but it was hardly a walk in the park and required a network of bases in Iceland, Greenland and elsewhere to support venturing further.
I was thinking of the leather coracles used in another voyage. I read this book: https://www.goodreads.com/book/show/1088116.The_Brendan_Voya...
Human walking speed is about 3.1mph. Walking 8 hours a day, it takes 40 days to cross a thousand miles. Communication's slow, but not that slow – especially if you've got horses. My working theory is that people walked.