I had a lot of issues with KDE connect and then I found out it requires some ports to be open. Try opening 1714-1764 with iptables and see if it improves.

I hate to say it, but I really wish Linux had the Microsoft Phone app. It’s far better in my opinion.