Your desktop probably already has mDNS set up, most user-friendly distros do it out of the box.
But it doesn't really matter, because KDE Connect implements its own sort-of mDNS system by itself, in the form of JSON broadcast across the local network on a standard port offering hostnames, services, and other metadata. Actual, real mDNS would require integration into the host's networking setup and that's too much to ask for clients like Android or iOS and you'd need to implement it manually in many other cases, so they kind of made their own mDNS. It also means you don't need root access to run KDE Connect on your device, which makes it viable on platforms like the Steam Deck.
To get KDE Connect working reliably, you need to make multicast traffic work reliably. Every network has its own restrictions when it comes to multicast so it's hard to know what specific tweaks your workstation needs. Having KDE Connect open on your phone, you should see packets coming in on your desktop on 255.255.255.255 on 1716/udp.
