パスワードの変更は数ヶ月前に試しましたが、しばらくするとまた同様のメッセージが表示されました。
ログアウト後ログインの作業も1月半くらい前に行ったと思いますが、改善しませんでした。
MacBook Air (11-inch Mid 2013), macOS Sierra 10.12.3
度々、失礼致します。
『パスワードの変更は数ヶ月前に試しました』とのことなのですが、変更は正常に完了していることを確認されたのですよね？ また、Apple IDに2ファクタ認証か、2ステップ確認を設定されていますか？
失礼致します。
通知パネル右下の「詳細」をクリックすると、何か詳細な情報が表示されませんでしょうか？
また、下記リンクも同様の状態ですが、一旦 iCloud からサインアウトする事で解決した様です。
（「ログアウト後ログイン」と言うのが、サインアウト後のサインインの事で有る場合は、スルーして下さい）
こちらのコメントも参考になるかもしれないです。 → Re: macのicloud設定で何度もicloudのパスワードが要求されます
カスペルスキーはインストールしてないですが、マカフィーがあるので、もしかしたら、関係あるかもしれないですね。
サインアウト後のサインインも試したのですが、しばらくするとまた同じ通知が出てきました。
「パスワードの変更を完了してください」というメッセージが出る
