I had to switch my Pixel C due to technical problems on the device, and I paired the replacement one before unpairing the old one. Now I can't unpair/remove it from the list of trusted devices. And since I don't have the old device anymore, I can't try connecting it and then unpairing.
This has been fixed in the upcoming version of KDE Connect, that is: unpairing a disconnected device deletes it. Until you get the update (which might be super late or never if you are on Ubuntu), you can try editing the config files in ~/.config/kdeconnect to remove the old device by hand.