Cato and UPnP (hole punching)

Cato Sockets do not have native support for UPnP (Universal Plug and Play) protocol. UPnP typically allows applications to automatically configure port forwarding on NAT devices, but since this functionality isn't supported by Cato Sockets, (I think) the peer-to-peer connection negotiation fails. Is this what is happening? You can check in PCAP while reproducing the issue. 

The connection works when remote users have the Cato Client installed makes sense because in that scenario, both endpoints are within the same logical network through the Cato Cloud, bypassing the need for UPnP-based NAT traversal. (theoretically it would make sense) 

For your specific use case with Parsec, you might need to:

Configure manual port forwarding rules in the Cato Management Application for the specific ports that Parsec uses. (more details here: https://support.parsec.app/hc/en-us/articles/32381460716180-Parsec-Connectivity-Requirements ) 
or
Consider using a different connection method that doesn't rely on UPnP
or 
Create bypass for this traffic, not sure if that is relevant in your case. 

You may always open a support ticket to get more details regarding this.