Was Shutdown actually malware?

No. Shutdown was never malware. It was a legitimate utility designed to shut down, restart, or log off Windows from the command line. Antivirus tools flagged it because the program performs power actions (like rebooting) without displaying a warning dialog, which matches behavioral patterns that security software looks for. This was a false positive.