After Tomcat installation, before I even changed the default Tomcat Manager password, the attacker used Tomcat Manager to deploy his own software. Probably some DDOS tools and a file manager.
I've already removed the suspected java software, changed all user passwords. Root login via ssh was not permitted.
How do I act now to ensure the server is secure?
What do I need to check?
How to trace any other suspected activity?
I will answer your first question:
Don't even try to clean it up if you can help it. Just reinstall the OS and this time setup firewall rules that block access to the Tomcat manager except from your current IP address. Even better just block everything except SSH and tunnel into the server then access the Tomcat Manager via the tunnel.
I think you should also read through the documentation for Tomcat Manager Setup.