Finally I was able to fix this issue for my situation. I posted a similar question on the Microsoft community pages, search for "Can't download song (0xc00d11cd or 0xc10100df)" as I can't post links here.
What fixed it for me was the following. Apparently I didn't have a save location anymore for my Music library, so it couldn't download my songs anywhere. So what you should check if you run into this problem is if you still have a save location. Right click on Music under library in Explorer and select properties. Check if any directory is still selected as save location. If not, create a new directory, add it there and select "Set save location". My guess is because I moved all of my music to OneDrive and deleted the original directory, the save location was deleted as well.