It seems you aren't the first person to run into this issue. Look at this link for an option. It's old but still seems to be helping people.

https://social.technet.microsoft.com/Forums/windows/en-US/9ee6ecdf-5958-4af4-b640-c659ada57bc4/option-to-create-new-folder-on-desktop-is-missing

A couple things to think about based on the comments in the link. It sounds like one or more different programs that were installed (and possibly uninstalled) could have caused this. It happens that I was just trying one of them the other day, but I don't seem to have this issue.

The solution involves merging a registry key file into your registry. As the source appears to be someone regularly posting on this Microsoft site and the comment/link has been allowed to remain, my trust factor went up a bit. I downloaded the reg file and viewed it in Edit mode. I don't see any red flags that could cause damage to your computer. I compared the settings to what I currently have and they appear essentially the same.

One of the commenters mentioned you have to be logged in as a user with full admin rights for this solution to work.

If you are nervous about getting this off a web link, you can go on a computer that is working and export the Folder section in the HKEY_CLASSES_ROOT section of the registry. Then merge the file that you created on your computer.