Well, traditionally the Scots in their legends said that we came from Scythia which is in that part of the world:

https://en.wikipedia.org/wiki/Scythia

From the 1320 Declaration of Arbroath:

"They journeyed from Greater Scythia by way of the Tyrrhenian Sea and the Pillars of Hercules, and dwelt for a long course of time in Spain among the most savage tribes, but nowhere could they be subdued by any race, however barbarous.

Thence they came, twelve hundred years after the people of Israel crossed the Red Sea, to their home in the west where they still live today."

http://www.scotsman.com/lifestyle/the-text-of-the-declaratio...

NB One of the kingdoms that eventually became Scotland was the Irish/Scottish Dál Riata:

https://en.wikipedia.org/wiki/D%C3%A1l_Riata

It wasn't referred to as the Black Sea, that was my summation of the journey as described in the legend. It is very similar to what arethuza posted about the mythical origin of the Scots.

I can't imagine the English name "the Black Sea" would have survived in Celtic, but it's interesting because the origins of the people and language appear to have been in Asia Minor (Galatia, modern-day Turkey).