With the help of this forum post and a bit of persistence I managed to get it to work and I wanted to share how with future generations and/or my future self.
First Problem: libstdc++.so.5
dnf does not have libstdc++5 but apt does.
Solution: I installed Mint on a Virtual Machine ran sudo apt install libstdc++5
and then copied the library to my real machine into the system directory of UT2004. The game now starts. I know there must be a better way to solve this.
Second Problem: Game starts in a tiny window stuck in the top left corner
Alt+Enter switches it to a real window that makes the game useable, but setting a proper resolution and trying to make it fullscreen again crashes the game.
Solution: Open /home/odin/.ut2004/System/UT2004.ini, go to the [SDLDrv.SDLClient] section and set all lines with viewport to the desired resolution.
Third Problem: No sound
UT2004 uses the obsolete OSS sound system.
Solution: Run the game under a compatibility wrapper. Debian and derivatives have aoss available. Fedora and derivatives have padsp. Thus run the game with padsp "./ut2004-bin-linux-amd64"
and the sound works.