Many VPN configurations break mDNS and other broadcasts (i.e. Chromecast, file shares, that kind of thing), though. A lot of "how to get started with WireGuard/OpenVPN/etc." guides stop the moment HTTP(S) connections work, but there's more to a functional network than that.
I found that I could get KDE Connect working on my buggy VPN profile by manually specifying remote IP addresses for devices on the other end of the VPN in the settings.
But it doesn't really matter, because KDE Connect implements its own sort-of mDNS system by itself, in the form of JSON broadcast across the local network on a standard port offering hostnames, services, and other metadata. Actual, real mDNS would require integration into the host's networking setup and that's too much to ask for clients like Android or iOS and you'd need to implement it manually in many other cases, so they kind of made their own mDNS. It also means you don't need root access to run KDE Connect on your device, which makes it viable on platforms like the Steam Deck.
To get KDE Connect working reliably, you need to make multicast traffic work reliably. Every network has its own restrictions when it comes to multicast so it's hard to know what specific tweaks your workstation needs. Having KDE Connect open on your phone, you should see packets coming in on your desktop on 255.255.255.255 on 1716/udp.