Well, I can only judge from the sites of cave-paintings and locations of mass slaughter of Palaeo animals in Europe I know of, and they were mostly far away from the shore. Major population migration routes along shores such as the Bering Strait crossing and the Aboriginal migration to Australia occurred mainly only in the very last part of the Palaeolithic era . But I admit that, at the very least, a small percentage of Palaeo humans must have lived near the shores at any one time.However, salt-mines were not started until the Neolithic era.

As regards Taubes, I should add that  natural salts are already found in (healthy) foods in sufficient quantities so there is no nutrient-based  reason to add extra table-salt or sea-salt. I'll grant that salt has often been used to add flavour to cooked foods, but  someone on a raw, palaeolithic diet doesn't need salt for that purpose.Plus, Taubes has a certain negative reputation:-

http://reason.com/archives/2003/03/01/big-fat-fake

http://reason.com/archives/2003/03/01/an-exercise-in-vitriol-rather

http://reason.com/archives/2003/03/01/gary-taubes-tries-to-overwhelm

Geoff