I have a Lenovo AIO system with Windows 10 64 bit.

I cannot connect any Bluetooth device to it. The devices are detected (most of the time). But when I try to pair it stays connecting for some time, then I get the message "we didn't get any response from the device. try connecting again".
I tried three devices (Phone, laptop and a wireless headphone) and none of those worked on my PC. I have another PC of the same build (bought together) and all three devices are connecting to it.

I tried reinstalling the bluetooth device and using the latest driver from the website. I also tried creating a new user account and it is still not working.

Is there any way to correct this problem, other than reinstalling the OS?