Ubuntu – How to make the Bluetooth keyboard work with Ubuntu 18.04

I just bought a new Bluetooth Keyboard, and it won't work with Ubuntu 18.04. Most of the time, pairing fails. On the rare occasions it worked, they keypress were laggy (delay after the press, or one keypress produces multiple characters) until the connection just dropped.

What I did:

• Paired the keyboard with my smartphone: it works
• Paired an Apple Bluetooth keyboard with my ubuntu: it works

I'm not familiar at all with bluetooth troubleshooting.

Using bluetoothctl, I tried to manually trust, pair and connect to the keyboard. Pair fails:

pair 76:11:02:01:00:C0
Attempting to pair with 76:11:02:01:00:C0
Failed to pair: org.bluez.Error.Failed

Here's the bluetooth service status:

XPS:~$ systemctl status bluetooth.service
● bluetooth.service - Bluetooth service
   Loaded: loaded (/lib/systemd/system/bluetooth.service; enabled; vendor preset: enabled)
   Active: active (running) since Sat 2019-04-20 11:24:42 CEST; 5h 53min ago
     Docs: man:bluetoothd(8)
 Main PID: 1053 (bluetoothd)
   Status: "Running"
    Tasks: 1 (limit: 4915)
   CGroup: /system.slice/bluetooth.service
           └─1053 /usr/lib/bluetooth/bluetoothd

avril 20 13:06:10 Eric-XPS bluetoothd[1053]: connect error: Host is down (112)
avril 20 13:06:29 Eric-XPS bluetoothd[1053]: Can't get HIDP connection info
avril 20 13:06:35 Eric-XPS bluetoothd[1053]: connect error: Host is down (112)
avril 20 13:06:51 Eric-XPS bluetoothd[1053]: Can't get HIDP connection info
avril 20 13:06:57 Eric-XPS bluetoothd[1053]: connect error: Host is down (112)
avril 20 13:07:09 Eric-XPS bluetoothd[1053]: Can't get HIDP connection info
avril 20 13:07:14 Eric-XPS bluetoothd[1053]: connect error: Host is down (112)
avril 20 17:03:23 Eric-XPS bluetoothd[1053]: 76:11:02:01:00:C0: error updating services: Input/output error (5)
avril 20 17:05:01 Eric-XPS bluetoothd[1053]: Refusing input device connect: No such file or directory (2)
avril 20 17:05:01 Eric-XPS bluetoothd[1053]: Refusing connection from 76:11:02:01:00:C0: unknown device

And here's the hardware:

Eric-XPS:~$ lsusb
Bus 004 Device 001: ID 1d6b:0003 Linux Foundation 3.0 root hub
Bus 003 Device 002: ID 0b95:7720 ASIX Electronics Corp. AX88772
Bus 003 Device 001: ID 1d6b:0002 Linux Foundation 2.0 root hub
Bus 002 Device 001: ID 1d6b:0003 Linux Foundation 3.0 root hub
Bus 001 Device 003: ID 0c45:670c Microdia 
Bus 001 Device 002: ID 0cf3:e300 Atheros Communications, Inc. 
Bus 001 Device 007: ID 0951:1665 Kingston Technology Digital DataTraveler SE9 64GB
Bus 001 Device 005: ID 1c4f:0026 SiGma Micro Keyboard
Bus 001 Device 001: ID 1d6b:0002 Linux Foundation 2.0 root hub

What do you suggest to troubleshoot and, ultimately, get this working?

EDIT:
After running more tests, it appears everything will work fine as soon as the laptop has never been to sleep. Sleep once, and I have to remove all bluetooth devices, reboot, pair again and it will work. It is not specific to the keyboard, the mouse shows similar problems.

I updated bluez as suggested on this page, but the issue is still here.