SOLUTION:
Older Visual Studio versions are known to cause problems with Unreal Engine.
Just open the project with the newest Visual Studio 2019 and you should get a message like: “Install … for Unreal Engine Automation tool” etc. just hit “install” and let Visual Studio download the missing parts.
Voilà, packaging works fine now.