There is actually an easy way to fix this without a lot of trouble. For the TL:DR people, the bold parts are relevant.
One thing to check first; if you have multiple store views, go into the product and switch the view to particular view. Scroll down and make sure the URL-Key is set to "Use Default Value". If that isn't checked, it will never generate. I think this can happen when you import M1 products. I had 200+ products that needed touched up.
This fix also helps if you do the trick where you switch your store to a different root and back, which cleans out everything. Including your custom ones. And it can finish with nothing but the category URL's. Not sure why the URL generation for products fails completely but I think it's because Magento is trying to make too many links in one operation which fails.
So give this a shot. Open the URL rewrite window and note the number of entries. This let's you know if it works.
Go into a first level category (it doesn't work on default because is doesn't have a URL key). Scroll down to Search Engine Optimization / URL-Key. Add an X to the end of the key. Uncheck the "Create Permanent Redirect for old URL", it only adds more work to the operation. Save your category.
Repeat the operation and remove the X, again uncheck the "Create Permanent Redirect for old URL", because you don't need those old URL's clogging up the table. Save again.
Refresh the URL rewrite page and you should see a new number, and shiny new URL's.
Repeat as needed.
FYI really big categories may time out. So in those cases, do the smaller sub-categories by themselves. On my server that threshold is about 400 entries.
Magento is smart enough to make the links for the category above your sub-categories. It is also smart enough that when it see's a product in another category, it builds the links for there too.
Took me a while to figure out why I was seeing fewer and fewer links added as I went down the category list. It was because a majority of products were already in the table and just the stragglers that hadn't appears before remained.