In Game Settings in our launcher, choose Cross Store MP (all players will have to do this). That makes you use the Nakama MP service instead of Steam's. Does that help?  

Any firewall in your computer or router will need to allow all traffic from steam.exe , stellaris.exe and Paradox Launcher.exe through in both directions. The issue won't be specific ports as Steam and Nakama use different ones.  

Well, again, Steam MP and Nakama MP servers will use different IPs to each other. The bottom of this page has links to the Steam IPs:

Steam Support :: Required Ports for Steam

help.steampowered.com
I don't have similar info for Nakama I'm afraid.

Finbarrr said: On a side note, I can play the game perfectly normally using a VPN with no issues.

That proves it is indeed a firewall issue!