Hi Kalificus,
Start Menu button can be manually started from this location- C:\Program Files\Classic Shell\ClassicStartMenu.exe. Does starting it from there put the button back on the taskbar and do you see it running in the Task Manager? If yes, then it's just not starting at startup reliably. Put a shortcut to that EXE in the startup folder. Check in Services.msc if the Classic Shell service is disabled. It should be set to Automatic and started. The service starts the Start Menu on Windows 8.