Macを再起動する度に「"AppleID"に問題があるため、このMacをiCloudに接続できません。」と表示されます。

このメッセージの前後にApple IDのパスワードを変更したりしてませんか？

Apple ID のメールアドレスやパスワードの変更後にやるべきこと - Apple サポート

Apple IDのパスワードがあまり強固ではないという可能性はありませんか？　こちらのサポートでは、　→　セキュリティと Apple ID - Apple サポート

パスワードは 8 文字以上にし、大文字の英字と小文字の英字を両方とも使い、数字も少なくとも 1 個入れる必要があります。パスワードにできるだけ多くの文字や英字句読点 (ピリオドなど) を追加してパスワードをより強力にすることもできます。

となっていますね。　あるいは、長い間、パスワードを変更してない可能性があるのかもしれません。

Takuya6781 による書き込み:

パスワード変更を行って1週間様子を見てみましたが、

なら、キーチェンアクセスも修正（余分なエントリの削除）をしとかないと、余計な原因を引き込むことになるけど。当然、他の端末でも再ログインは必須になる。

Takuya6781 による書き込み:

AppleIDの変更はここ半年行っていない状態で、エラーは発生し続けております。

またAppleID更新を行って1週間程度様子を見てみましたが、改善しないようです、、、

Apple IDはそもそも、よほどのことが無ければ変更するものではない。

変更する場合も、一定の手順に沿って変更しないと、今回のような面倒を引き込むけど、そのせいでは？

度々、失礼致します。　

xyさんもご指摘ですが、一度、ログインキーチェインをリセットしてみるか、

　→　キーチェーンに問題がある場合　（macOS El Capitan）

iCloudキーチェインをオフにして様子を見てみるとどうでしょうか？

ログインキーチェインは（macOS Sierraの場合）、 ~/Library/Keychains/login.keychain-db　ですので（El Capitanの場合は、拡張子が.keychainだったかもしれません）、これをバックアップしておいて、キーチェインアクセス.appの環境設定から、リセットのコマンドを実行します。