I had a similar problem, but with an iPad. Nearly posted a question, but then after I asked Bluetooth to remove the device I was trying to pair it to, I tried again! And it worked. So try the following:
Close, unplug the devices for 10 seconds
In Bluetooth, ask to remove the device you were trying to pair to
Then try to pair again and cross your fingers!