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?
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.
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