whoever is interested:
My requirement is that players do not have to do port forwarding, even if they are hosting a server.
Steam (SDK) supports this, but I couldn’t get it working using the Steam OSS plugin and the Steam Sockets Plugin.
However, after days of failures, I found this thread which seem to be highly related to what Im trying to archieve: Question about networking ports and EOS - #10 by NomNomai
EOS (SDK) implements NAT-Traversal + Relay Servers. The pre-built-in plugin for EOS doesn’t use it, but maybe this one: https://www.fab.com/listings/b900b244-0ff6-49e3-8562-5fc630ba9515 (at least one of the pictures says “No portforwarding needed”) 
Update
Until anyone proves the opposite: Session making without any port forwarding is not possible when hosting a dedicated server (at least not out of the box when using Steam or EOS Plugins). You need to use the listen server model!
Answer to the original question: NAT punch etc. seems to work for the dedicated server, but its still required to open ports.