First things first you need to have a new ish bluetooth adapter I have found in my testing.
It may need to be bluetooth 4 compatible I am not sure but my laptop and phone worked whereas my desktop using a £1 dongle did not.
Once you get a successful pair you may notice the controller still has a blinking light. If this is the case see below.
Install sysfsutils
sudo apt-get install sysfsutils
Edit the config to disable bluetooth ertm
sudo nano /etc/sysfs.conf
Append this to the end of the config
/module/bluetooth/parameters/disable_ertm=1
Reboot your machine.
sudo reboot
Then you need to repair the device. So forget the device in bluetooth settings and repair it.
Now it should have a solid light on the controller and all is good.
Tested on Ubuntu 18.04.