I have a Microsoft Wireless Notebook Bluetooth Mouse 5000 for my laptop, when I go mobile. I like this mouse, because it doesn’t have an extra dongle that eats up a USB port. When I just booted my laptop up, my mouse wasn’t connecting. It had been working fine the last time I used it, several months ago. I tried to break the pairing from the PC and reconnect it, but it seemed like the process wasn’t completing. Windows 8 showed the mouse as a registered device, but the Green/Red pairing sequence kept happening on the mouse. I had been doing the pairing from the “classic” interface. I switched over to using the Metro version of the “devices” app, that can be found via “Settings”. When I repaired the mouse, it worked successfully.
This is the Metro screen I used to do the pairing.