Как соединить php и vue?

И вообще, насколько целесообразно использовать такой стек?

Стек фронтенда не влияет на стек бэкенда. Вполне целесообразно.
Ваш JS на фронте посылает запрос на бэкенд и получает ответ. Какие используются фреймворки на фронтенде и какой стек на бэкенде не важно.

Как я понимаю, через rest api?

Конкретно REST с его 5 ограничениями вам не нужен, у вас просто обмен данными по http, в любом удобном вам формате.
В некоторых обучающих материалах любую API использующую http как протокол зовут REST, или говорят что это про использование GET/POST/PUT/DELETE глаголов, или формирование URL`ов, но это просто популярное заблуждение. Об этом не стоит париться.