There is no trace (historical or archaeological)

What sort of traces would we be looking for? After all, there are those who suggest an essentially Shamanic foundation for the stone circles, ritual landscaping and rock art going back 7,000 years - and yet further given the hunter-garther migrations & recent findings at Göbekli Tepe which push back the envelope rather and are analogous to what we find in the UK at a later date. That we find Shamanic practise enduring as far afield as Lapland and the Amazon basin then it might be reasonable to suppose that pre-Xtian / prehistoric UK were similiarly disorientated. I'm sure even Aubrey Burl suggested as much - after all antler head-dresses have been found (even in Lancashire) conforming to the classic image. Where there is readily available hallucinogens / inebrients and tribal culture, there will be some form of Shamanism involved. And weren't the Druids themselves essentially Shamans? There are those that suggest that Christ himself was an initiate, and that Celtic Mythology is full of Shamanic / Bardic / Druidic references - Taliesin, The Tain, The Voyage of Bran and The Song of Amergin all!

I wonder - does Kaledon Naddair still hang around Auld Reekie? He was the self-styled Keltic / Pictish Shaman. And some of those Göbekli Tepe pictograms have a Pictish feel about them...