I've set up a phone with Rethink DNS as a permanent VPN, so nothing can come through, I tried putting KDE Connect in the Bypass Universal list, but it still fails to discover devices on the network and in turn it can't be discovered by others itself.
I tried without VPN active and it all works, of course. Is it possible for the 2 to coexist? If so, what settings should I change?
Sounds like a problem specific to RethinkDNS. The by-pass setting on my VPN provider works great. I didn't have to do anything else.