KDE Connect on Fedora 25 and my Android phone couldn't pair up, even after I added my desktop hostname to the phone. The issue is you need to open the necessary ports in your firewall. There are ways to do this (in Fedora, open Firewall Configuration program and in Zones > Services check the kde-connect service), but the average user will have no idea what the problem is and has to luck into finding the fix.
Perhaps as Fedora bug 1279190 suggests KDE Connect could detect that the ports it needs are blocked by a firewall, and warn the user. At least that would give the user a hint as to what to fix. https://community.kde.org/KDEConnect#Troubleshooting documents the steps for ufw and Firewall Configuration.
(Thanks for a great utility!)