iCloud says "Password is wrong", but I think it's correct. How should I proceed?
Head over to https://iforgot.apple.com/ and follow the procedure there, including contacting Apple Support if everything else fails.
When an account gets locked - even the correct password won’t work so talking to someone that can help you in a locked account situation is the best strategy since they will also be sure you’ve used the correct troubleshooting steps like checking system date, restarting the device, trying another network based on what their dashboard shows for your account.
I was encountering the exact same problem when trying to setup an iCloud email account on my Android - I got stuck setting up the incoming mail server. The issue was that I needed to create an App specific password. Once generated, I was able to use this password and continue setting up the email account.
Hope this helps someone else too!