К методам
messages.* получить доступ могут только standalone-приложения. Это приложения, работающие без помощи браузера. Например, клиенты (официальные приложения VK, Kate Mobile, Snapster и т.д.). А у вас тип приложения "веб-сайт".
Вы ничего не сможете с этим поделать и заставить работать Open API с сообщениями не получится. Единственный выход - кидать пользователя на страницу получения токена в вашем standalone-приложении и просить скопировать его в форму на вашем сайте, а затем уже с сервера с этим токеном делать запросы. Но это плохо влияет на UX хотя бы потому, что на странице, откуда пользователь будет копировать этот самый токен, жирным написано, что копирование токена может быть небезопасным.
