I was going insane with this same issue for almost a month now, and I had it all working two months ago. (The store isn’t officially active yet so it wasn’t as dire as it could have been), I tried all the options mentioned in this thread hoping one of them would apply to my issue, but nothing worked. I finally did what I should have done a month ago and that is disabled every plugin and then re-enabled them one by one until I found what was interfering with generating download permissions. It turned out to be the plugin “jonradio Shortcodes Anywhere or Everywhere”, and I don’t even think the plugin itself inherently conflicts with Woocommerce digital downloads, because I had the same version of that plugin enabled when I had everything working properly, so I assume my issue was either a plugin setting, or some sort of short-code that I had somewhere like a header and forgot about.
Anyway, I just thought I should post my experience, as maybe it will save someone, who has the same issue as I did, the time of going through all their plugins to debug the issue.