I would recommend you to first remove the complete bluetooth configuration and then try to repair all needed devices. Run the following commands in Terminal:
sudo systemctl stop bluetooth
sudo rm -Rf /var/lib/bluetooth/*
sudo systemctl start bluetooth
If you are still unable to pair using the graphical method, please follow the instructions in the thread below to use the command line for it:
Then, if your problems still persist, please let us know.