すこしはまったのでメモします。

結論・解決策・確認ポイント

管理画面　→　設定　→　表示設定　→　1ページに表示する最大投稿数
ここで設定している数値と
WP_Queryの引数、プロパティposts_per_pageを比べます。

wpquery.php


$args     = array(
    'posts_per_page' => 5
);
$my_query = new WP_Query( $args );

ここで
1ページに表示する最大投稿数　＞　posts_per_pageだと
私の場合2ページ目のリンクを踏んだ時
ページが見つかりませんと出てしまいました。
posts_per_pageの数値を大きくすると問題が解決しました。

状況

Wp_queryで一覧画面を作成。
paginate_links関数でページャー、ページネーションを設置していた。

起こった問題

2ページ目以降が表示されない
『ページが見つかりません』
と出てくる。

ソース

pagenation.php


$paged    = get_query_var( 'paged' ) ? absint( get_query_var( 'paged' ) ) : 1;
$args     = array(
    'category_name'  => single_cat_title( '', false ),
    'paged'          => $paged,
    'post_type'      => array( 'page' ),
    'posts_per_page' => 5,
    'page'           => get_query_var( 'page' ),
);

$list_query = new WP_Query( $args );
if ( $list_query->have_posts() ) :
    while ( $list_query->have_posts() ) : $list_query->the_post();
        ?>
        <article class="BlogPagePost">
            <h2>
                <?php the_title(); ?>
            </h2>
            <?php the_excerpt(); ?>
        </article>
    <?php endwhile; ?>
<?php else: ?>
    <p>まだ記事がありません</p>
<?php endif; ?>
<?php

if ( $list_query->max_num_pages > 1 ) {
    //リンク形式を指定
    if ( get_option( 'permalink_structure' ) ) {
        $format = 'page/%#%/';
    } else {
        $format = '?paged=%#%';
    }

    //ページ送りを表示
    echo paginate_links( array(
        'base'      => get_pagenum_link( 1 ) . '%_%',
        'format'    => $format,
        'current'   => max( 1, $paged ),
        'total'     => $list_query->max_num_pages,
        'mid_size'  => 2,
        'prev_text' => '&larr;',
        'next_text' => '&rarr;'
    ) );
}
// クエリとページネーションをクリーンアップ（メインクエリを再設定）
wp_reset_postdata();

はまりポイント

前述した以外にもいろいろと原因があるようです。
自分で経験したポイント以外は書くと混乱を招きかねないので
以下さわりだけ書いてみます。

WP_Queryのoffset パラメータをセットすると paged パラメータを無視します。そのためページ送りされません
固定ページではWP_Queryのpagedパラメータを設定する必要がある
WP_Queryのmax_num_pagesパラメータが取得できていない
wordpress管理画面→設定→表示設定→フロントページの表示の設定が関係することがある