I just bought 2 brand new Pixel 9a phones. Well, as far as I can tell they are brand new... original boxes that look factory sealed, etc....
I've successfully installed GrapheneOS on both phones. They are working fine as far as I can tell except for KDE Connect. It works fine on one of the two new Pixels. I can see my old Pixel 7a phone and my desktop which is running Fedora 44 Linux.
However, KDE Connect does not work at all on the second Pixel 9a. That phone sees no other devices despite me refreshing and trying to pair a new device (obviously it cannot as it sees no other devices).
The only difference between the two phones (as far as I know) is that the one on which KDE Connect is working has no SIM card in it.
I found this topic, but it didn't help.
https://discuss.grapheneos.org/d/18712-unable-to-get-my-phone-to-connect-to-kde-connect-or-local-send
The problem cannot be a VPN as my VPN is disconnected on both phones and on my desktop.