SUMMARY The verification key shown is wrong when the other device has been paired before, but has since changed certificate. STEPS TO REPRODUCE 1. Pair a device 2. Change certificate/key on the other device 3. Perhaps restart KDE Connect Android (not sure if required) 4. KDE Connect Android now shows the device as remembered device currently unavailable 5. Unpair it 6. Now it shows up in Available devices and you can pair it but the verification key is wrong. You can force stop and restart KDE Connect Android at this point, and the verification key is correct. I don't have 100% conclusive proof that it's the other side certificate, but IMO that's a very plausible reason for the effect I'm seeing.