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

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

管理画面　→　設定　→　表示設定　→　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管理画面→設定→表示設定→フロントページの表示の設定が関係することがある