В случае, если кто-то найдет этот вопрос и ему понадобится ответ, я обнаружил проблему: документация неверна, заголовок авторизации требует проекта SERVER KEY облачного обмена сообщениями. Это НЕ то же самое, что общий ключ API.
Здесь вы можете найти правильный ключ по состоянию на октябрь 2019 года:
Google, пожалуйста, сохраните вашДокументация в курсе, я потратил впустую часы, пытаясь выяснить это!