This was an awesome hint. I could trace down the permission error and could see that Discourse was using a different user. Now to the big why and why nobody had this error before.
We have a custom plugin for sending Push Notifications through AWS SNS which was setting credentials through Aws.config.update globally and therefore S3 Backup seems to also have been using the wrong credentials that obviously did not have the required permissions.
We will now fix our plugin to locally provide the credentials/region and support EC2 IAM roles which i am preferring at this point 
Thanks for the push in the right direction!
paresy