Speculating here based solely on general networking knowledge. You may have "AP Isolation" enabled and/or multicast blocking on your network may be causing problems.

If I was working on KDE Connect I would add a microphone and speaker based pairing system using OFDM modulation lifted from Rattlegram. Each device would share all IP addresses associated with themselves using sound to broadcast the information.