Missing Paste special options in Excel 2010

First, try to run in safe mode : Excel.exe /Safe (in the run command) if that works correctly there, that means that it's due to either an add-in or a workbook that is loaded at startup.

(File>Options > Addins - uncheck all Addins) Note which ones were selected. Close Excel and then reopen it

If that works, then one of the addins was the issue, just have to find which one by reenabling them one by one.

If this didn't work, then it's probably due to one file located in the startup directory of excel. (ie C:\Program Files\Microsoft Office\Office14\XLSTART for me)

Any file in there is loaded when you start Excel. Remove the files out of that folder and open Excel to see if the problem is gone.

if that works, add them back one at a time, closing and reopening Excel each time until you determine which file was corrupted.

I had the same issue and removing (or put it on 'disable') the add-on 'Skype Click to Call' from Skype in the IE-browser under Internet Options and the tab 'Programs' - 'Manage add-ons', it was solved. Seems that the new Skype version is adding this 'add-on'.