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.
Maybe local DNS/DHCP resolution issue? I have this on my LAN with with other services and hosts: the Dnsmasq drops the ball every now and then and does not update the lease database, which results in hosts seemingly being offline.
I would try fixed IPs to see if this solves the issue for you.
