Deputado e Presidente de Província

O ministério de 13 de setembro de 1832 sobreviveu por quase quatro anos e quando Manuel do Nascimento Castro e Silva foi encarregado, em 1835, de compor um novo governo, convidou Paulino (carta de 12 de janeiro) a ocupar a pasta da Justiça. Recusou, alegando não ter "forças suficientes". Não poderia recusar, contudo, o convite de Evaristo da Veiga para concorrer a deputado provincial, nas eleições para a Assembléia recém-criada pelo Ato Adicional, que separou a cidade do Rio de Janeiro da Província, criando o Município Neutro. Em 1836, como deputado provincial, começa sua luta contra o federalismo confuso criado pela legislação de 1834 e sua ambiguidade na definição de empregados gerais e empregados provinciais.

Seu projeto de reforma do federalismo brasileiro não começa, portanto, de uma posição no governo geral, mas da experiência de deputado provincial. Comenta o autor da Vida do Visconde: "As bases da interpretação estavam assentadas antes mesmo da existência do Partido Conservador. Paulino, com uma visão perfeitado futuro, prepara e desenvolve a obra da reação conservadora, quando ainda não existiam os conservadores" (pág 47).

Incluído na lista de vice-presidentes da Província, ocupou o cargo interinamente no impedimento de Rodrigues Torres em 22 de abril de 1835 e definitivamente após a exoneração deste, em 1836. A nomeação, de forma irônica, é feita pelo Regente Feijó. No dia 30 de abril de 1836, presta juramento como Presidente da Província do Rio de Janeiro, o segundo desde sua criação. Tinha então 29 anos de idade.