Ubuntu 20.04, Bluetooth True wireless headphones not working (work in previous version) Sony WF-1000XM3
I had the same problem. reading your question I realized that you were right, the headphones never warned me that it was connected so they were still in pairing mode.
Once the pairing was done I turned them off, then turned them on again and it worked without problems.
Greetings my friend.