Segundo José Pedro Machado (Dicionário Etimológico da Língua Portuguesa), o particípio de licenciar, licenciado, tem sido usado como nome para designar um título universitário, desde 1331. A abonação de origem galega que este lexicógrafo faculta sugere que se trata, de facto, de um título ligado ao direito e à aplicação da lei: «estando preso e julgado a morte por llos liçençiados R. da Rocha e R. A.».
O sentido de licenciado no exemplo dado pela pergunta confirma que a palavra é aplicada a alguém com estatuto social prestigioso, o qual é marcado pela palavra senhor. Tudo isto é confirmado pelo artigo “Licenciado” do Dicionário de História de Portugal (organizado por Joel Serrão, Porto, Livraria Figueirinhas), no qual, além de se explicar que o grau de licenciado é bastante antigo nas universidades europeias, se esclarece que «[n]o século XVI o título de licenciado [itálico no original] constituía, no quadro do funcionalismo régio, tanto em Portugal como na Espanha, um importante degrau de valorização social, sobretudo no ofício da justiça».