Can't sign into Apple ID on MacBook Air

Are you running any anti - virus programs? Using a VPN?

Try setting up another admin user account in System Preferences/Users & Groups to see if the same problem continues. Please post back on whether or not this worked. Also try the Safe Mode. Please post back on whether or not this worked.

Isolating an issue by using another user account 

Safe Mode - About

If it works in the Safe Mode, try running this program when booted normally and then copy and paste the output in a reply. The program was created by Etresoft, a frequent contributor.  Please use copy and paste as screen shots can be hard to read. Click “Share Report” button in the toolbar, select “Copy to Clipboard” and then paste into a reply. This will show what is running on your computer. No personal information is shown. If the log won’t post, try posting it in Pastebin and provide a link in a reply. After pasting the report in a PasteBin page, go to the top of the page, and copy the address in the URL bar. Paste that in a new reply.        Pastebin

Etrecheck – System Information

I have essentially the same problem as the OP and after trying many things—I have reset my password on the Apple web site, I have tried signing out and back in again, I have asked iCloud to remove my iMac and then signed back in using the 6 digit code sent to my iPhone (both of which make my iMac reappear in the list of 'My Devices') but still I can't get my new password accepted in the 'Update Apple Id Settings dialogue.

I have tried safe mode with the same result. However, I can successfully set up iCloud in a new user account.

It may not help, but try running/posting the Etrecheck report in your normal account. If the log won’t post, try posting it in Pastebin and provide a link in a reply. After pasting the report in a PasteBin page, go to the top of the page, and copy the address in the URL bar. Paste that in a new reply.        Pastebin

Some people have solved this by going to System Preferences/Internet Accounts, selecting an iCloud account there, and signing in. You need to repeat this for each iCloud account.