Never mind, I used LockHunter to delete both these folders and used this method with FRST to remove entry from Windows Security Center which was still present. Rebooted after each step and then installed Kaspersky Free again, rebooted and Context menu options are back.
A user shouldn't have to do all this at all. Uninstaller needs to be more precise and thorough while removing Kaspersky, let's just say right now it doesn't look good.