When promoting Custom Objects and their security, we have to look at Custom Object Permissions (after loading the respective Profiles and Permission Sets in addition to the Custom Objects). We should follow a similar model for Custom Settings and Custom Metadata Types. The reason is that, if they remain part of the Profile or Permission Set, then I have to make sure that the Profile or Permission set exactly matches what I want in the target environment - I can't have any extra Custom Settings or Metadata Types that don't exist in the target environment yet or the promotion will fail.
Where I ran into this is we have Field Trip in a lower environment but don't intend to promote it into Prod. So now the users can't view any Field Trip information in the lower environment, since I can't give them access to it unless I'm also willing to put Field Trip in the target environment (prod).