Na verdade Camões chama-lhe apenas «velho d'aspeito venerando». A palavra Restelo não aparece sequer uma vez nos Lusíadas. Mas o velho proferiu o seu célebre discurso na partida de Vasco da Gama para a Índia, que nós sabemos ter acontecido na antiga praia do Restelo. E é por essa razão que autores posteriores o apelidaram de Velho do Restelo.
Restelo era ao tempo de Vasco da Gama o nome da zona hoje conhecida por Belém, em Lisboa. A mudança do nome deveu-se à construção no local do Mosteiro de Santa Maria de Belém, mais conhecido por Mosteiro dos Jerónimos, mas o nome Restelo sobrevive um pouco mais a poente no atual bairro com esse nome. Uma variante antiga no nome é Rastello (Damião de Góis (1502-74), Cronica de D. Manuel), e foi sugerido que na sua origem estivesse o rastelo, uma espécie de pente de ferro para trabalhar (rastelar) o linho (Wikipédia).
Nos Lusíadas o «velho de aspeito venerando» surge entre a multidão que se despede dos marinheiros de partida para a Índia, e começa famosamente o seu discurso com
Ó glória de mandar, ó vã cobiça
Desta vaidade a quem chamamos Fama
e continua com uma crítica veemente à expedição e a aventuras ultramarinas em geral, prevendo calamidades para os marinheiros e o reino. Daí ele se ter tornado num símbolo do pessimismo e conservadorismo. No entanto isto parece ter acontecido tardiamente. Procurei no Google Books, e parece ser em meados do século XIX que começam a aparecer comentários políticos e sociais em torno da personagem. O primeiro exemplo que encontrei é de 1853 no Estudo moral e politico sobre Os Lusiadas de José Silvestre Ribeiro (p. 132; grafia original e ênfase minha em todas as citações seguintes):
E o caso he que por todo o Reino se pensava do mesmo modo por que se exprimia na praia o velho de aspeito venerando […] Os vaticínios do velho verificarão-se, desgraçadamente, pelo andar dos tempos, pois que Portugal só conserva as gloriosas recordações […]
A primeira referência ao velho desligada de uma discussão dos Lusíadas, encontrei-a num debate acerca da marinha brasileira nos Annaes do Parlamento Brazileiro de 1879, onde ele é referido por velho dos Lusíadas:
As condições da guerra hoje podem não ser as mesmas que eram no tempo em que o velho dos Lusíadas gritava vendo afastar-se da praia os navios portuguezes :
Ah maldito o primeiro que no mundo
Nas ondas vela pôz em secco lenho
É do ano seguinte, 1880, a primeira ocorrência que encontrei da expressão Velho do Restelo, na História de Portugal de Joaquim Pedro de Oliveira Martins:
Camões fulminava, pela bocca do velho do Restello, os que arrastavam Portugal para o mar ; como Plutarcho tambem condemnou Themistocles por ter lançado os gregos no caminho das emprezas maritimas.
E finalmente, encontrei o primeiro uso metafórico da expressão numa introdução a um projeto de Constituição apresentado por José Soares da Cunha e Costa ao Parlamento português em 1911 (As Constituintes de 1911 e os seus Deputados; obra composta e dirigida por um antigo official da Secretaria do Parlamento, p. 437):
A hora, porém, não é de desalentos, é de esperanças, e não serei eu o Velho do Restello n'esta data que a tanta gente enche de orgulho, de commoção e de fé !