query_posts：2ページ目の表示は正しいが、個別記事のリンクが1ページ目と同

どんなテーマのどのテンプレートファイルのどの部分に書かれたのでしょうか？
このコードの部分だけみても答えが導き出せません。

こんにちは、

サンプルコードを試してみてください

以下の例は、固定ページテンプレート　Query Post Test　を選択した場合のものですが、
他のテンプレートファイルの中でも、動作すると思います。

ただ、設定・フロントページの表示やカスタマイザーで、フロントページに設定した場合は、動作しません。

もし、gurokazuさんがフロントページで、このページングをする場合は、home.phpというテンプレートを作成して、以下のコードを記述する事で動作すると思います。

同様にトップページとして表示される front-page.phpというテンプレートもあり、一応こちらでも、動作するようでしたが、home.phpを使用する事をおすすめします。

<?php
/**
 * Template Name: Query Post Test
 */
	$paged = get_query_var('paged');

	if( empty( $paged ) ) {
		$paged = 1;
	}

	query_posts( 'posts_per_page=4&paged='.$paged );

	while ( have_posts() ) {

		the_post();

	?>
	<li>
	<a href="<?php the_permalink();?>"><?php the_title( );?></a>
	</li>
	<?php

	}

	posts_nav_link('｜', '<span class="next">< next</span>', '<span class="prev">previous ></span>');

	wp_reset_query();
?>

あと、ループ処理の部分は、一般的なPHPだと連想配列なのでforearch文を使いたくなると思いますがwhile文で行ったほうがいいです。

while ( have_posts() )

で記事の件数だけ繰り返し、

the_post();

で、1件分のデータを取得しています。
gurokazuさんのコードだと、forearchで1件、the_postで1件という風に記事の取得を2回行う形になっています。

WordPressのPHPは独自の関数を使い、ちょっと変わった書き方になっていることも多いので、デフォルトのテーマの中でどのように処理をしているか読んでみてから、ご自分のコードに応用したほうが無駄がないコードがかけると思いますよ。