I had Sony CH-WH710n and no major problems.

Try to pair the headphones via bluetoothctl and see if there are any errors in the logs.

Do you dual boot windows? In my case it couldn't pair to both at the same time without extracting the keys.

I would try to see if windows pairs up with the headphones, after all other troubleshooting steps are exhausted.