2 часа искал решение, зарегился, задал тут свой вопрос, и в течение следующих 5 минут сам нашел решение.
Дело в плагине All in One Seo Pack. "aiosp_paged_format".
Заходим в общие настройки, и там в разделе "Настройка заголовков" Формат для навигации. Меняем значение с "Part %page%" на "Страница %page%" и все работает.
Может кому полезно будет.
