My issue was that that same device was already paired for debugging over USB. I turned off USB debugging on the device and did Revoke USB debugging authorisations. Then I could pair over WiFi using the QR code.