The reason for messages going into SPAM is because Email Clients aren't able to validate the sending email server versus the domain keys set on the domain.
In Sitecore EXM, there is a Domains page where you register all of the domains that Sitecore Cloud EDS is using. Each one will provide DKIM keys that need to be correctly added to the domain of each sending domain.
Short of that, the From Email Address is configured in the Email Manager Root, although you may also manually specify a From Email Address when creating an email campaign. It is best practice to have a separate Manager Root for each Domain that you are sending from.
And while not a requirement of Sitecore Cloud EDS, it is best practice to setup appropriate SPF records too.