The issue doesn't seem to be related to the cloud managed profiles / certificates: I've just manually created a new provisioning profile with type "App Store", and despite "User Assigned Device Name" is listed in the "Enabled Capabilities", the .mobileprovision file doesn't contain the entitlement. A provisioning profile with type "Ad Hoc" contains the entitlement.

I've got the same issue with our cloud managed certificates. The entitlement is included in the provisioning profile for development ("iOS Team Provisioning Profile"), but not in the profile for distribution ("iOS Team Store Provisioning Profile"), despite "App Store" is listed in the capability's distribution restrictions. As I'm finding here several threads about this topic, is there a general issue with the handling of this entitlement for cloud managed profiles / certificates? Yesterday, I've written an email to developer (at) email.apple.com, but haven't received an answer yet (honestly, I don't know if this address is supposed to receive mails... I've just answered to the entitlement confirmation mail)

I can confirm this issue. There is no option in the Web-UI to enable "Access to Cloud Managed Distribution Certificate" for an API-Key.