O erro de “insufficient permissions” aconteceu porque você pediu um token com scope nfse e depois tentou fazer uma consulta de CNPJ. Para isso você precisaria pedir um token que tivesse o scope cnpj, o que foi feito na sua segunda tentativa.
Quanto à obtenção do token, é isso aí mesmo, e está explicado em detalhes na documentação neste capítulo sobre autenticação, incluindo a parte do scope mencionada acima. A sua solução inclusive está mostrada quase que exatamente igual, na seção “Exemplo de requisição para obtenção do token”:
