Open any office program, click the orb in the upper left corner, click whatever Options (ex: "Excel Options"), click "Resources", look for "run Micorsoft Office Diagnostics" and click Diagnose, when the "Is Micorsoft Office having problems" box appears click continue and it will run the repair and should fix your shortcuts as well.
Let us know what happens. Good luck.