Delete all previously paired devices and pair them again. This usually helps.
For the command-line, man bluetoothctl …
man bluetoothctl