So what happened when you tried suggestion number 5? Did the headphones work with other devices (which would suggest that the problem is in how your phone connects with those headphones), or did they have the same problem (which would put the problem unambiguously with the headphones themselves, or at least between those headphones and this particular phone)?
I've never had a problem with Android failing to switch the output to a bluetooth audio device when it connects, so this is not normal android behaviour (and I'm using an s21 on the latest update, so the software should be very similar to your phone). It feels like either a misconfiguration of the headphones or a miscommunication between them and the phone when they connect. Do these headphones have a companion app (some do)? If so maybe check its settings, or clear its cache or data.
Maybe also check in your sound settings: in the sound settings there's a "Separate app sound" option that allows you to tell some apps to always play through a different audio device. I've never used it, but maybe check that there's nothing set there that might interfere with this connection.
As for clearing the bluetooth cache, normally when "clear cache" is greyed-out for an app that means that the cache is already empty - though in my case it's greyed-out even though it isn't empty (not quite: there are 14kB in there), so obviously Samsung just don't want you doing that.