Papai Noel, como o tdmsoaes já averiguou (ver outra resposta), é uma adaptação do francês. Segundo a Wikipédia, o Père Noël (literalmente, Pai Natal) aparece na literatura francesa em meados do século XIX, correspondendo ao Father Chirstmas britânico e ao Santa Claus dos Estados Unidos, sendo este nome uma adaptação do Sinterklaas (São Nicolau) holandês.
Luís da Câmara Cascudo conta-nos no seu Dicionário do Folclore Brasileiro que Papai Noel chegou ao Brasil na segunda década do século passado, tendo-se vulgarizado depois dos anos trinta, por «iniciativa oficial e letrada, jamais popular».
Mas já se encontra Papai Noel (ou papá ou papae) na imprensa brasilieira a partir de 1898:
“Chronica”, Gazeta de Noticias, Rio de Janeiro, 25 de dezembro de 1898, p. 1.
Encontram-se na Hemeroteca Digital Brasileira cerca de 70 ocorrências de papai Noel entre 1900 e 1909, contra 420 na década seguinte). Também se encontra esporadicamente papai Natal, logo a partir de 1899:
“Chroniqueta”, Gazeta de Noticias, Rio de Janeiro, 24 de dezembro de 1899, p. 2.
Em Portugal a primeira ocorrência de pae Natal no Google Books é em 1911 pela pena de Antero de Figueiredo na revista portuense A Águia (grafia original e negrito meu em todas as citações):
Porque emquanto vocês esperavam pela vinda do Pae Natal, carregado de brinquedos e bombons
Pai Noel aparece também em Portugal. O primeiro exemplo que encontrei foi no semanário humorístico Sempre Fixe de 13 de Janeiro de 1927 (p. 6):
No Governo Civil, ante um mascarado descalço, de «Pai Noel»:
—Como explica esse disfarce?
—Aproveitando a tradição desta noite preparava-me para recolher calçado.
E parece que ainda por cá continuou (em Portugal) uns tempos. Veja-se a queixa na revista Portucale: Revista de Cultura em 1940:
O presépio desapareceu, desapareceu o Menino-Jesus, e lá de fora veio, para os substituir, a «árvore do Natal » e o « Pai Natal », também por aí chamado « Pai Noël »! E as lojas, pelo Pôrto fora, ostentavam a « árvore » e o « Pai Noël », cobertos de neve, muita neve
Portanto parece que o senhor foi importado de França para o Brasil e Portugal mais ou menos na mesma altura. Em Portugal acabou por ficar pai Natal; no Brasil vingou papai Noel.