Your firewall needs to open input TCP ports 1716, 1739-1741
KDE Connect app on your phone will use TCP ports >1023 as source port
You also need to allow input UDP port 1716.
KDE Connect app on your phone will use UDP 1716 as well as source port.
If you’re blocking outbound then you also need to allow TCP output to ports 1716, 1739-1740 and UDP to 1716
Even though you disabled firewall you need to make sure no rules from nftables or iptables exist such as default block rules.
While trying to connect you need to open up and tail firewall log to observe dropped traffic.
I don’t know how this is done with firewalld but with nftables you configure logging to separate file.