They aren't in short supply, but aren't present everywhere - e.g. in Europe there's nothing north of Slovakia. If Denmark wants storage, they have to work with other countries and rely on transit. It's even worse for the Baltics.
Edit: I was a bit puzzled as there are already pumped-storage plants in Wales and Scotland with more planned.