I have the same issue, very frustrating. I thought it was a firewall issue, or Android's blocking LAN connections without a VPN, but at this point I'm pretty sure it's just some KDE Connect bug.
I would try fixed IPs to see if this solves the issue for you.