It would have been nice if you had mentioned which registry cleaner?
Not to mention what OS you are using?
Playing with the registry can seriously damage your system, be it using a registry cleaner or manually.
Without knowing what you did within the registry cleaner, it is hard to say what to do, but most registry cleaners worth their salt should have an option (usually a default action) to backup/copy stuff that it/you elect to delete.
If so you should have been able to restore that set of deletions and hopefully that should have restored things.
Now that you have used Last Known Good Configuration (LKGC) I don't know if the action above will work. You should really have sought help before trying system restore/LKGC.
I have no idea what you mean by 'Should I do a non-destructive F10'?
Did you try your friend google? I did and it returns lots of hits for 'restore start button and task bar' without the quotes, hopefully there is something there.
http://www.google.co.uk/search?q=restore+start+button+and+task+bar