複数カテゴリーを持つ投稿をsingle.phpで一つのカテゴリー毎にページ送りしたい

思いついたのは WP_Query で category__in と date_query を指定する方法ですね。
ループ内に以下のPHPを書いてください。

// カテゴリIDの配列
$categories = get_the_category();
$cat_ids = array();
foreach ( $categories as $category ) {
    $cat_ids[] = $category->term_id;
}
// 現在の投稿の日時
$post_time = get_the_date('U');
// 前の投稿のクエリ
$prev_query = new WP_Query(array(
    'posts_per_page' => 1,
    'category__in' => $cat_ids,
    'date_query' => array(
        'before' => $post_time,
    ),
    'order' => 'DESC',
));
// 前の投稿のURL
if ( $prev_query->have_posts() ) {
    $prev_query->the_post();
    $prev_post_link = get_permalink();
}
// 次の投稿のクエリ
$next_query = new WP_Query(array(
    'posts_per_page' => 1,
    'category__in' => $cat_ids,
    'date_query' => array(
        'after' => $post_time,
    ),
    'order' => 'ASC',
));
// 次の投稿のURL
if ( $next_query->have_posts() ) {
    $next_query->the_post();
    $next_post_link = get_permalink();
}
// 投稿データのリセット
wp_reset_postdata();

「親ページのカテゴリ」というのが、複数のカテゴリの「いずれか」なのか、「すべて」なのかがわからないので、とりあえず「いずれか」のほうでコードを書きましたが、「すべて」にする場合は category__in を category__and に変更してください。

すみません、コードにいくつかミスがあったので訂正します。

// カテゴリIDの配列
$categories = get_the_category();
$cat_ids = array();
foreach ( $categories as $category ) {
    $cat_ids[] = $category->term_id;
}
// 現在の投稿の日時
$post_time = $post->post_date;
// 前の投稿のクエリ
$prev_query = new WP_Query(array(
    'posts_per_page' => 1,
    'category__in' => $cat_ids,
    'date_query' => array(
        array(
            'before' => $post_time,
        ),
    ),
    'order' => 'DESC',
));
// 前の投稿のURL
if ( $prev_query->have_posts() ) {
    $prev_query->the_post();
    $prev_post_link = get_permalink();
}
// 次の投稿のクエリ
$next_query = new WP_Query(array(
    'posts_per_page' => 1,
    'category__in' => $cat_ids,
    'date_query' => array(
        array(
            'after' => $post_time,
        ),
    ),
    'order' => 'ASC',
));
// 次の投稿のURL
if ( $next_query->have_posts() ) {
    $next_query->the_post();
    $next_post_link = get_permalink();
}
// 投稿データのリセット
wp_reset_postdata();

変わったのは以下の2点です。

$post_time = $post->post_date;

「投稿日時」のフォーマットを勘違いしていました。

    'date_query' => array(
        array(
            'before' => $post_time,
        ),
    ),

*_query のご多分に漏れず、一つ一つをネストした配列に入れるのを失念していました。

さて、ループへの組み込み方ですが、あなたのコードは <a> タグ内の変数を echo していない点を除いて間違っていません。
間違っていたのはこっちでした。

「関係のないカテゴリーへも不規則にリンクされてしまい」とは、投稿1のカテゴリAとは無関係のカテゴリCに属する投稿3にリンクされる、という意味でしょうか。
そうであるなら、WordPressの仕様通りであり、俺のコードの意図する通りですのでなんら問題ありません。
そうでなく全くの無関係の投稿にリンクされるとすれば問題ですが。

個別投稿ページの「親ページ」とか「元のページ」というのがカテゴリアーカイブページである、という認識に違和感があります。
ページAからリンクしてもページCからリンクしても、投稿1の内容は同じですし、それを判別する仕組みはWordPressにはありません。
「ページAから来た場合」と「ページCから来た場合」で投稿1の内容を変えるには、URLのGETパラメータ（クエリ文字列）やCookieを使って判別するくらいしか思いつきません。
例えば、ページAにある投稿1へのリンクにはURLに ?category=A を付ける、投稿1ではURLのGETパラメータからリンク元を知り、ページ送りの内容に反映する、とか。
後者は if ( isset($_GET['category']) && $_GET['category'] == 'A' ) といった感じでわりと簡単に判別できますが、前者はお使いのテーマ次第ですね。
不可能ではないですが、その場合色々と検討する必要があります。

• どのページからのリンクにどのようなGETパラメータを付けるか
• GETパラメータがない場合（カテゴリ以外のページから来た場合）、どのように表示するか
• 思わぬGETパラメータが与えられた場合にどう対処するか

それより、厳密に同一カテゴリ内でのページ送りが必要で、かつひとつの投稿が複数の（それぞれが無関係の？）カテゴリに属する、とはどのような形態なのか、よくわかりません。
投稿が単一のカテゴリのみを持つようサイト構成を見直す、というアプローチもあると思います。

なるほど、理解できました。
そのような分類を行う場合にはカスタムタクソノミーというのを使うのが一般的だそうですが、カテゴリでもできないことはありません（カテゴリもタクソノミーの一種です）。
例：カスタムタクソノミー「色」……緑色、白、黒、etc.
　　カスタムタクソノミー「生き物」……カエル、スズメ、猫、etc.
いずれにせよ、リンク元を判別する必要はありますが。

確かに、特定のカテゴリに属する投稿を片っ端から読みたいという場合はありますね。
そういう場合、普通はカテゴリアーカイブのページにいちいち戻って次の投稿を探す、というふうに使うものだと思います。
しかし、ページ送りの要領で次の投稿に遷移できれば、楽ではありますね。
投稿が属するカテゴリの分だけページ送りを設置する、という方法だと比較的簡単に実装できそうですが、全くスマートな方法ではありませんね……

カテゴリアーカイブのページのテーマファイルで、投稿へのリンクのURLを出力する部分にフィルターフックを設置するなどして、出力するURLをGETパラメータ付きに書き換えれば、個別投稿ページ側でリンク元を判別することができます。
また、個別投稿ページからページ送りによって前後の投稿に遷移する場合も、GETパラメータを維持するようにすればよいでしょう。
それらの実装についてはやはりお使いのテーマ次第（特にカテゴリアーカイブのページのテーマファイル）、ということになります。
よって、ここでコードをお示しすることはできませんが、情報をいただければ時間のあるときにコードを書いてみたいと思います。

すみません、また間違えました。
一つ目のコードの1行目を次のように訂正します。

function add_category_param( $permalink ) {

フックする関数の引数が1個より多いときは add_filter() に第4引数を与えなければならないのですが、引数は1個しか使っていないので指定しないことにしました。