First, we appreciate the script, in the future it would be nice for Defender to have a roll back / reply feature or similar to other anti-virus products on the market, however, customers need to also be aware that this did not only affect the Start Menu in ProgramData but also the Start Menu in AppData/Roaming for the signed in user. The issue also affected C:\Users\Public\Desktop and C:\Users\<username>\Desktop or C:\Users\<username>\OneDrive\Desktop, luckily for us we use OneDrive to protect Important Files so these links were in the Recycle Bin for OneDrive online. Pernille-Eskebo - your script should also check to see if OneDrive is protecting their Desktop to restore these files too as lots of people have shortcuts to websites, folder paths, etc. (not just applications).
As a thought for others, we took copies of the Start Menu (ProgramData and AppData/Roaming) from a computer that was not affected and zipped them and created a simple Powershell script in Intune to download the zip and extract (overwrite) to the appropriate folders. One script ran as system (to restore ProgramData) and the other ran as the users credentials (to restore AppData/Roaming).
Regards,
Jason B.