I imagine that isn't what you want to hear, but I am afraid to say I do not believe Start8 is the cause of your problem.

Once uninstalled Start8 is removed (though double check the program files directory to ensure the Start8 folder has been completely removed) assuming you rebooted afterwards.

Nobody has ever reported anything even remotely similar to the best of my knowledge either and Start8 does not alter any system files and other that the setting to make it boot to the desktop vs the Start Screen (adjustable in the OS from the taskbar properties too), does not alter any OS registry settings either.

Unfortunately I suspect something else has caused your OS to stop showing this menu and I am curious as to what you mean by the right click options not working with Start8 either as by default we show our own menu (though we have a setting to show the OS one instead).  This is going to sound really dumb, but you have checked your mouse right click button is working correctly?

You might also want to try using Winkey + X as that should make the very same menu show up.  If that does not work then it sounds like something has perhaps altered group policy to prevent that menu from showing up at all.  If that works then have you installed anything else which may extend the taskbar in anyway as it may be blocking right click messages even getting to the taskbar.

Just for clarity I must again point out that Start8 cannot damage your system any more than say Notepad can.