I have experienced problems connecting my Bluetooth mouse with Linux (in my case: Fedora 29). The problem was that after the first pair through the Gnome Settings UI, the Comfort Mouse was not able to reconnect to the PC.
To solve the problem, simply use the command line tool bluetoothctl to pair and trust the device. Here are the steps in detail:
Open a terminal (as user) and type in
The tool now starts and shows you whats happening with your bluetooth devices. Turn on your bluetooth mouse and long press the connect button to set it into pair mode. You will see a new message like this:
[NEW] Device xx:xx:xx:xx:xx:xx Microsoft Sculpt Comfort Mouse
Now copy the MAC Address of the device (here xx:xx… etc) and type:
pair xx:xx:xx:xx:xx:xx trust xx:xx:xx:xx:xx:xx
Now your mouse is paired and should reconnect automatically. Leave the bluetoothctl program by pressing ctrl+d