Sharepoint Shortcuts - 404 Error Page not Found

HI Matthew I believe the "Recent Documents" is a pre-built Content Search Web Part. 

First, I would add the "Recent Documents" to a new page and see if it works.  If it does, then it tells you the web part on the other page is just broken and either replace it or inspect the web part properties to see what's wrong with the query.

If it doesn't work by adding the Recent Documents to a new page in that it gets teh documents, but the URLs don't work then you have a larger issue that may need Microsoft's attention.  Is this SharePoint On Premise or SharePoint Online?

Good luck!