I haven't quite understood yet why it's apparently no problem to use music at other competitions. I mean are there special rights for the Olympics

Weird (oh, sorry, just saw, someone already asked that...but still haven't seen a very understandable answer).
No, I'm 99% sure there are no special rights for the Olympics, but the Olympics has a significantly larger TV audience than any other skating event. So there' s potential there for the big record labels (e.g. your Warner Music or Sony Music) to not be that worried about their artists' work being broadcast to a niche audience or streamed by diehard skating fans, but they will want to extract $$$ as the Olympics is still a high rating television event across both traditional linear television and now streaming.
Basically, it's about ratings, potential audience reach and how they can monetise that.
A skater at a small club competition is likely going to get away with not clearing music because there will be no broadcast and very few audience members, and nobody is making money from that competition. As soon as you introduce a large paying audience and broadcasts/streaming then people (music labels, artists, lyricists, composers, orchestras) might potentially want their cut. Some artists might be very happy for their work to be used for free but it's often not just them who has a say (the aforementioned music labels), and others will either see it as a commercial opportunity or just not want their work used in that way.
I think people skate to covers for many reasons, but covers do tend to be cheaper to license.
There are whole YouTube channels of (bad) covers out there, some of which have been used for skating programs - I've joked before about there being an ISU Bad Cover Shop. My educated guess is that these are popular because the work of clearance with the original artists has already been done, so it's just the cover versions which needs to be cleared and it is indeed cheaper.
Maybe these artists are saying "sure you can use my music as long as it's not for a really big comp?"
Per above, that is indeed what I think is happening. Not certain, but I would say highly likely.
ETA: I'm not qualified to provide expert copyright advice, but in my working life I have to have a knowledge of copyright.