Check your Firewall, Router and VPN Settings
The KDE Connect protocol requires ports 1716-1764 for TCP and UDP to be open. Auto-discovery requires UDP broadcasts.
The KDE Connect wiki has further information about using OpenVPN and configuring firewalls.
Hope this helps!