When attempting to add (pair) a new bluetooth device, if no devices are detected it may be that the ‘Bluetooth Support Service‘ is disabled or stopped. Check this by going to:
Start->Run->compmgmt.msc->Services and Applications->Services
Make sure the status for service ‘Bluetooth Support Service’ is ‘Started’ and the startup type is ‘Automatic’. After starting this service, you should now be able to add bluetooth devices to Windows. Starting this service also enables display of the bluetooth settings dialog, which the Windows help points out should be visible in the Control Panel when you search for ‘bluetooth’. Another symptom that this service is not running is that when you right-click the bluetooth system tray icon and choose ‘settings’, nothing happens (i.e. no dialog appears).
To Microsoft: Surely it would have been simple to check whether this service is running before doing bluetooth device discovery or opening the settings dialog, and at least report to the user that they need to start the service (or do it for them ideally) rather than just failing silently.