How to add email aliases to users synched with Azure AD sync tool

Adding them via the proxyaddresses attribute (or even better, using the Exchange management tools) on-prem is the correct way to do so. Note however, that O365 will only allow aliases associated with domains you have verified with the service, all others will be replaced with generic user@tenant.onmicrosoft.com ones.

If the changes you made on-prem are not syncing, it might be due to duplicate values or some other error. Check the event logs and any errors in the MIIS Client. Here's a nice troubleshooting article: https://azure.microsoft.com/en-us/documentation/articles/active-directory-aadconnectsync-service-manager-ui-connectors/#follow-an-object-and-its-data-through-the-system

That is what I have done.
The mail alias is on an domain that is correctly associated with office 365. In the local AD the user has the correct proxyaddresses.
Azure AD sync service says that sync was successful and I can verify it in Synchronization service manager.
But sender gets this mailerdeamon response: 550 5.4.1 [tester@domain.com]: Recipient address rejected: Access denied

Mail delivery can fail for a number of reasons, not only because of missing aliases. Have you actually checked whether the alias is synced to Azure AD? Try these:

Get-MsolUser -UserPrincipalName user@domain.com | select -ExpandProperty proxyaddresses
Get-Recipient user@domain.com | select -ExpandProperty proxyaddresses

Select allOpen in new window

Using the your commands I can see that the alias is not synched.
I can see the alias in the active directory under the user's properties -> Attribute editor -> proxyAddresses

And Azure AD sync service says that sync was successful and I can verify it in Synchronization service manager. It clearly shows that it wants to add the proxyaddress and it reports back that the sync was succesful.
But the alias does not show up in Office 365 or in Exchange Online management.

Very strange..

As I wrote above, there can be some issue with duplicate attribute values or similar. It's hard to guess like that, so use the article I linked to above to get more info on the issue. Also check the event logs and the email notifications send by the dirsync service.

Some of the errors might be visible on O365 side as well, but that's not always the case. You can get them with:

Get-MsolUser -HasErrorsOnly | ft DisplayName,UserPrincipalName,@{Name="Error";Expression={($_.errors[0].ErrorDetail.objecterrors.errorrecord.ErrorDescription)}} -AutoSize

Select allOpen in new window

I tried the command that but it does not return anything. No error nor any info. It just runs and the nothing???

This simply means that O365 hasnt flagged any users with errors. You can still have errors on dirsync side, as explained above.

Ok. thanks.
I am somewhat slow here - what du you mean "dirsync side"?
Should I look somewhere else than Synchronization Service Manager?

You should check the object properties in the Metaverse, as per the article I posted above. And check for any errors in the email notifications that should be received by the Technical contact email for you tenant.

I figured out the problem by myself.