確かに設置するだけでGoogle検索のようなページネーションが表示されるのですが…。
自分が作っているサイトはURLを全て日本語にしているためバグが発生。
少なからず日本語（/%category%/%postname%/）のようなパーマリンク設定を
されている方はいらっしゃるのでは？？
かつWP No Category Baseをインストールしバグが発生している件も多数検索で
見かけます。
僕の場合は掲載されている情報だけではバグが直らなかったので自分で調査。
そして発見！
まず日本語のURLをソースで確認すると
/%E5%95%86%E5%93%81%E4%B8%80%E8%A6%A7/
このように大文字アルファベットに記号のURLが並びます。
これがバグの元凶でした。
全て小文字にする事で解決します。
しかし、ただHTMLをゴリゴリ書き換えるのはプログラマーとして残念な事になるので
プラグインの中身を直接修正します。
【ディレクトリ】/wp-content/plugins/wp-pagenavi
wp-pagenavi全てダウンロード。
wp-pagenavi内のcore.phpを修正します。
232行目あたり
return "$text";
赤色の部分を書き加えて完成です。
これで綺麗なページネーションができるようになりました。