I had the same problem and all my drivers were up do date.
What worked for me was:
- Open Device Manager
- In Bluetooth tab, find Microsoft Bluetooth Enumerator
- Disable it (ignore the warnings)
- There, I was told to restart my PC for the changed to take effect.
- After the restart, my PC was unable to connect to my headphones or even detect them. My Bluetooth mouse worked just fine.
- Enable the driver again.
- My PC automatically connected with my headphones and worked just fine.
If this does not work, try disabling the Microsoft Bluetooth Enumerator LE instead.