First, a caution: Do not retry passwords. Trying random passwords or wrong passwords more than (usually) twice, and that'll usually trip evasion, and you'll get blocked even with the right passwords. If you've retried random passwords, you'll have to let things "cool off" for a while, and try again later.
Open up the details drawer in the Mail.app Connection Doctor troubleshooting, and re-run the connection tests. Expurgate anything sensitive from the diagnostics, and post the iCloud-related errors here.
Alternatively, remove the iCloud account from the accounts listed within Mail.app. Re-add it. See if that clears the issue.
Alternatively and if the other options here fail, contact Apple iCloud support directly and request assistance.