KDE Connect not recognising device

Hello! I cannot make my device recognised on Android 13 (GrapheneOS). I reached out to Graphene OS forums already:

I am using a VPN, but on my old device (Android 10, EMUI), KDE Connect works regardless of whether there is a VPN connection.

But I cannot figure out what the issue is. Any ideas on how to approach this challenge?

You could try manually specifying the IP address in KDE Connect to see if that helps, but I would be making sure your VPN isn’t tunneling LAN traffic.