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?
if you use Android's built-in setting to set up DNS instead of using an app that uses the VPN slot, you might have more success.
also, you might want toggling "block connections without VPN" off in system settings, I had to disable it when using KDE Connect with Mullvad.
I'd like to use Rethink DNS (forcefully set to DNS+Firewall) because it keeps a record on-device of the connections that apps tried to establish. So as I understand it's not possible to have both then?
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.
Turning on "Block connections without VPN options" will not make KDE connect work. Your solution is, either to keep this setting turned off, or use Rethink using another device. By using another device, I mean, set up Rethink either on your router, or maybe an old Android with Rethink installed and using using it as a hotspot with "Allow clients to use VPN" option (which is available on LineageOS, but not on GrapheneOS). Or you can also set up something like piHole.
Turning on "Block connections without VPN options" will not make KDE connect work
I did do that in conjunction with bypass set for KDE connect only and it works. I find the other options you suggested really cool though! Might give them a shot.
Also didn't know about the share VPN thing, I've wanted that for so long! Weird Graphene doesn't have it as well