They somehow do get recognized as a bluetooth device, but not as an audio headset. At the same time, my Pixel connects to them without any issues and plays sound just fine.
I guess we have slightly different models, but mine seems to indicate that I need to turn it on and continue holding the power button for 7 seconds to pair it with a new device.
Alright so the solution for me was to hold the 2 sensors simultaneously for a short amount of time and then fedora fially recognized them. There was nothing wrong with my codec support or bluetooth config or hardware (as I use uBlue, just so you know). But then I had to also manually set them as audio output device in sound settings.