TL;DR

PauseHandler#postメソッドを使う場合はhandleMessageメソッドではなくdispatchMessageをoverrideする
最終的な実装はgistに置いた：PauseHandler for Handler#post method

PauseHandlerとは

FragmentのライフサイクルではonSaveInstanceState以降にFragmentを触ろうとするとIllegalStateExceptionが送出されます。
これは、GUIの状態を一時保管するタイミングであるonSaveInstanceStateよりも後にFragmentの状態を変えるために起こります。
アプリがバックグラウンドに回るとUIスレッドは動作を中断しますが、ユーザーが好き勝手に作ったワーカースレッドは特別に操作をしない限り動き続けます。
したがってワーカースレッドからUIスレッドにGUIの更新を要求するアプリだと上記の状況は容易に起こりえます。

これを解決するためには以下のどちらかの処置が必要です。

onSaveInstanceStateが呼ばれた後のUIスレッドへの要求は破棄する
onSaveInstanceStateが呼ばれた後のUIスレッドへの要求はキューに溜めておいて、onRestoreInstanceStateで復帰した後にキューから取り出して受理する

つまり、捨てるか溜めるかですね。

上記の処置はFragmentクラスに実装してもよいですが、UIスレッドへの要求には通常Handlerクラスを使うことを考えるとHandlerクラスを継承した独自クラスに実装する方が筋が良いといえます。

この独自クラスは俗にPauseHandlerと呼ばれています。

android - How to handle Handler messages when activity/fragment is paused - Stack Overflow

このPauseHandlerを使用するFragmentクラスでは、PauseHandlerにonSaveInstanceState/onRestoreInstanceStateのタイミングを知らせるために、onPauseでPauseHandler#pauseを、onResumeでPauseHandler#resumeを呼び出しておきます¹。
この呼び出しさえしておけば、あとはPauseHandlerに対して通常どおりsendMessageを呼び出すだけでPauseHandlerの中で適切に上述1または2の処置を実行してくれるのです²。

……sendMessageだと？

オリジナルの`PauseHandler`の問題点

Handlerへの要求の出し方は大きく2つあります。
Messageインスタンスを渡し、別途設けたコールバックで要求内容の中身を把握しながら要求を実行するHandler#sendMessage系メソッド³を使う方法と、Runnableインスタンスを渡して要求内容の中身を見ずに実行するHandler#post系メソッド³を使う方法です。

StackOverflowのPauseHandler実装はHandler#sendMessage系メソッドには対応しているものの、Handler#post系メソッドには対応していません。
実際にPauseHandler#postを実行してみると、FragmentのonPauseが呼び出された後であってもアクション（引数に指定したRunnableインスタンス）は破棄されずキューにも溜められず、通常どおりUIスレッドで実行されてしまいます。

それもそのはず。
StackOverflowのPauseHandler実装はHandler#handleMessageをoverrideすることで破棄またはキューへの積み込みを実現しているのですが、このメソッドが呼ばれるのはHandler#sendMessage系メソッドだけでHandler#post系メソッドでは呼ばれません。

解決方法

解決方法は単純明快。
Handler#handleMessageではなくHandler#dispatchMessageをoverrideすればよいのです。

Handlerクラスの実装を見てみるとわかりますが、Handler#dispatchMessageはHandler#sendMessageとHandler#postのどちらの場合でも呼び出されます。Handler#dispatchMessageはsendMessage経由から呼ばれたかpost経由で呼ばれたかの振り分けを行っており、呼び出し元がHandler#sendMessageだった場合はHandler#handleMessageを呼び、呼び出し元がHandler#postだった場合はRunnableインスタンスのRunnable#runメソッドを呼ぶ仕組みになっています。
よってHandler#dispatchMessageに処理を介入させられればどちらの場合でも対応できるのです。

修正した私家版PauseHandlerのコードを以下のとおりです。
ただし、簡単のため、1, 2の処置の切り換えを実現していた抽象メソッドstoreMessageは廃し、単純にコンストラクタに引数で与える形にしてあります。

public class PauseHandler extends Handler {
    private boolean mIsPause;
    private boolean mStoresMessages;
    private final Queue<Message> mQueue = new LinkedList<>();

    public PauseHandler(boolean storesMessages) {
      super();
      mStoresMessages = storesMessages
    }

    public PauseHandler(Callback callback, boolean storesMessages) {
      super(callback);
      mStoresMessages = storesMessages
    }

    public void resume() {
        mIsPause = false;

        while (!mQueue.isEmpty()) {
            Message msg = mQueue.poll();
            if (msg != null) {
                sendMessage(msg);
            }
        }
    }

    public void pause() {
        mIsPause = true;
    }

    @Override
    public void dispatchMessage(Message msg) {
        if (mIsPause) {
            if (mStoresMessages) {
                Message copied = Message.obtain(msg);
                mQueue.offer(copied);
            }
        } else {
            super.dispatchMessage(msg);
        }
    }
}

本当に単純です。
違いはoverrideの対象がhandleMessageメソッドからdispatchMessageメソッドになったことと、processMessageがなくなった代わりに親クラスのdispatchMessageメソッドを呼ぶようになったことだけです。
このクラスを使用すればpost系メソッドであっても上述の1または2の処置どおり期待どおりに動作します。

public class AFragment extends Fragment {
    
    // ...

    private PauseHandler handler = new PauseHandler(true);

    // ...

    public void aMethod() {
        // ...
        handler.post(new Runnable() {
            @Override
            public void run() {
                // UIスレッドで実行したい処理。
                // 普通のHandler#postを使う場合と使い方に違いはない。
            }
        });
        // ...
    }
}

もちろん、sendMessage系メソッドもオリジナルのPauseHandler同等に動作します。オリジナルのPauseHandlerでは抽象メソッドprocessMessageがコールバックインタフェースになっていましたが、修正版のPauseHandlerではhandleMessageを直接、コールバックにしてしまえばよいです。

public class AFragment extends Fragment {
    
    // ...

    private PauseHandler handler = new PauseHandler(true) {
        @Override
        public void handleMessage(Message msg) {
            // 以前はprocessMessageに書いていた処理をここに書く。
        }
    };
}

もしくはCallbackインタフェースを継承したインスタンスを与えてもよいでしょう⁴。

public class AFragment extends Fragment {
    
    // ...

    private PauseHandler handler = new PauseHandler(new Callback() {
        @Override
        public boolean handleMessage(Message msg) {
            // 以前はprocessMessageに書いていた処理をここに書く。
            return true;
        }
    }, true);
}

上記を使いやすいようにリファクタした最終形はgistに置いたコードを参照してください。Android Studioが自動変換で作ってくれたKotlin版のコードもあります。

PauseHandler for Handler#post method

おわりに、あるいは記事を書いた動機

Handlerを使うときはsendMessageよりpostを使うことの方が多いんじゃないかなって思うんですけど、PauseHandlerでググってもdispatchMessageをoverrideするやり方は見つからなかったです。
ので、この記事が誰かの参考になれば嬉しいです。

「おいおい、onSaveInstanceState/onRestoreInstanceStateじゃなくてonPause/onResumeで呼ぶってどういうことだよ？　誤記か？」と思われるかもしれませんが、誤記にあらず。onRestoreInstanceStateはライフサイクルの中で常に呼ばれるコールバックではありません。pauseの設定/解除の確実な状態遷移とタイミングの対称性を保つために、onSaveInstanceState/onRestoreInstanceStateの前後にあり、かつライフサイクルの中で確実に呼び出されるonPause/onResumeを使用しているのです。 ↩
PauseHandler#storeMessageの戻り値がfalseであれば1、trueであれば2を実行します。 ↩
どちらのメソッドにも指定した時刻に実行する*AtTimeメソッドと、指定した時間だけ遅延させてから実行する*delayedメソッドがある。 ↩ ↩²
というよりこれがHandlerでMessageを取り扱う際の推奨されるやり方だ。 ↩