I'll look closer into this when I'm back at the computer in about an hour. In the post on the KDE forum, they seem to get an error complaining about the version though, while in my case they don't show up at all when I attempt to pair. I've checked the things listed on the KDE Connect wiki, but those checks pass.
EDIT: UDP discovery was turned off on my phone, and turning it on allowed connection. All is good now!