Old Macbook air(or any old Mac) could not connect to App store/iCloud using AppleID
Recently I experienced this issue and couldn't figure out why.
Solution:
It was solved by updated the default MacOS version to a later version by downloading/installing the latest supported MacOS using Command+Option+R combination when start the Mac with Internet connection, and select the version of MacOS you want to download and follow the steps to get the installation done.
This was not documented anywhere from my initial search online.
I hope it helps others with similar issue