CityCat4

Никак. Тем более между Казахстаном и Арменией. Если бы хотя бы одна из сторон была в Европе или РФ, где приличные скорости (это не означает, что там везде приличные скорости, но есть места...) - тогда можно было бы что-то кое-где у нас порой... А так - никак.
VPN будет работать по тем же проводам и ходить через те же каналы, да еще на шифрование тратить мощности. Да, его могут блокировать (и Армения, и Казахстан, и РФ, если через нее идет).
В теории можно поискать некий VPN, который улучшит пинг, на практике все будет упираться в сто тысяч факторов, ни на один из которых не повлияешь

Изменился маршрут между магистральными узлами. Теоретически можно написать в саппорт, практически Вас отправят в игнор - физик, с вопросом по игре...

Как повлиять на провайдера?

Никак.

А если это такая туша, как РТК - дважды никак. Только отказ от него и возврат на старого провайдера (если это возможно). РТК - это одна из тех тушек, которой все, вот совершенно все - пофигу. Ну нет у Вас столько денег на юристов :)
(Другими такими тушками являются Сбербанк и Почта России)

Изменения в DNS вносятся отнюдь не мгновенно - вообще говоря кэш может содержать старые данные до двух суток. Обычно три-четыре часа уходить на применение изменений.

С тем, что по wifi не бывает стабильной связи.

ping vk.com, mail.ru - свободно, есть обмен пакетами

Что полезного даст юзеру пинг ВКонтактика? Да ровно ничего :) Проверка не имеет смысла.

файл hosts на локальной машине чистый

В корпоративном окружении при заблокированных настройках адаптера не имеет смысла - нет прав админа, файл hosts не исправляется.

в браузере страницы не открываются.

Настройки прокси открываются? Прокси установлено?

Если настроено прокси, если в нем есть списки ограничений - то в зависимости от этих списков и параноий тех, кто их ведет и ими управляет - либо плагин с VPN наружу, либо никак :)