Behind the scenes, the Office 365 Exchange Migration tool is using Outlook to connect to Exchange. The scenario you are trying to perform will dictate how to create the profiles.
Almost all scenarios connect to Exchange Online. So the first step would be to try and create a profile for the Administrator account that was specified on the Remote PowerShell connection screen of the Office 365 Exchange Migration tool. Creating the profile verifies the admin account does indeed have a mailbox and Autodiscover is working properly. If you have a scenario where you autodiscover record is pointed at the On Premise environment you can check the Use Direct Discover option, which will cause the Office 365 Exchange Migration tool to bypass the normal Autodiscover process and try and connect directly to Office 365. Another common workaround is to try and create the admin account with a @domainname.onmicrosoft.com primary email address and login. The autodiscover record for that domain should always point to Office 365.
When Migrating from On Premise Exchange, one of the most common issues is mailbox permissions. Again, this is something that can be tested manually. First, create a profile for the Admin account specified on the Source Exchange Details Screen. Can Outlook connect to the Admin mailbox on the Exchange Server? If so, then attempt to add the account your are trying to migrate to that profile. Can you open that mailbox and browse the contents? If not, then the Admin account does not have the appropriate permissions.