Fulano, de acordo com o dicionário Houaiss (Lisboa, 2003), vem do árabe fulān, que significa ‘alguém, um certo, determinado (indivíduo)’; também se encontra no português antigo fuão e fulan.
A origem das outras duas palavras é mais incerta, mas uma opinião comum entre os filólogos citados no Houaiss é que ambas foram adotadas ou alteradas para rimarem com fulano, o que faz sentido já que beltrano e sicrano são quase sempre usadas com fulano, e fulano parece ser a mais antiga das três palavras.
Beltrano é segundo Antônio Geraldo da Cunha (Dicionário Etimológico Nova Fronteira da Língua Portuguesa) o nome próprio castelhano; segundo Antenor Nascentes vem do nome português equivalente, Beltrão, com a terminação alterada para -ano para rimar com fulano (Houaiss).
Sicrano tem a origem mais problemática. Cito o Houaiss, desabreviando as abreviaturas:
sicrano […] ETIM origem controversa, José Pedro Machado (Dicionário Etimológico da Língua Portuguesa) considera vocábulo de origem obscura, levantando a hipótese de ser talvez uma formação expressiva para rimar com fulano; compare com o espanhol zutano (1438 sob a forma çutana), vocábulo de origem incerta, segundo Corominas, que, no entanto, sugere tratar-se de uma interjeição cit! ou çut!, empregada como forma de chamamento e, logo, para nomear um desconhecido qualquer, cujo nome se ignora e, finalmente, adaptada à terminação de fulano; o espanhol apresenta diversas variantes, entre as quais cicrano, citrano, cistrano, formas que, segundo o autor, asseguram a indissociabilidade entre o espanhol zutano e o português cicrano;
Ciclano ou siclano, forma que o Bruno Lopes me trouxe à atenção, é uma variante de sicrano comum no Brasil e que também já se usou em Portugal, mas que eu desconhecia. Não vem nos dicionários, e não falta gente a dizer que “é termo inexistente” (aqui) ou que é “errado” (aqui). Mas a palavra aparece já em 1720 no Vocabulario Portuguez e Latino de Raphael Bluteau, ainda que no verbete sicrano, portanto sem direito a verbete próprio. Depois parece desaparecer dos dicionários, mas encontra-se em várias publicações em Portugal no século XIX, e até ao presente no Brasil.
Exemplos mais antigos
Encontrei fulan, fuan e foan, na versão portuguesa das “Flores de las leyes”, provavelmente do século XIII (o que confere com o dicionário Houaiss), já que o original é desse século (ver em Jácome Ruiz, o autor). As palavras aparecem numas fórmulas para o requerente se dirigir ao rei, em que fulan, etc. aparecem no lugar dos nomes relevantes. Exemplo (negrito meu):
[…] eu fulan me vos querello de fuan que me ouve de pagar en tal dya c. maravedis que lly emprestey e nõ mos pagou
“Versão portuguesa das ‘Flores de las leyes’”, Revista da Universidade de Coimbra, 1917, p. 358
A forma fulano aparece no século XV; segundo Fernando Venâncio (Dobletes e formas divergentes no português, p. 4-5) terá sido um cultismo influenciado pelo castelhano: formas populares que se tinham formado pela supressão de enes e eles intervocálicos, foram “corrigidas” pela reintegração dessas letras. Aconteceu com muitas outras palavras; por exemplo latim gelus > português antigo geo > gelo (mas ainda temos geada), latim opponente > português antigo opoente > oponente.
O sicrano mais antigo conhecido do Houaiss é de 1587; uma sicrana, na verdade:
Não vedes aquilo mana
não me afogo entã pouca agoa
olhayme a dona sicrana
Jerónimo Ribeiro, “Auto do Físico”, em Primeira parte dos autos e comédias portugueas, 1587, folha 106
Mas merece também menção um exemplo para aí um século depois, numa tradução portuguesa da Bíblia (Rute 4:1):
E Boaz subio á porta, e assentou se ali; e eis que o redimidor, de que Boaz tinha fallado, hia passando ; e disse lhe, ó fulano ou cicrano, desvia te para cà, assenta te aqui : e desviou se para ali, e se assentou.
A Biblia Sagrada, traduzida por João Ferreira d’Almeida (1628-91)
Podem ver que traduções posteriores, como esta e esta outra usaram um estilo um pouco diferente.
O ciclano mais antigo que conheço é mesmo a menção do dicionário do Raphael Bluteau em 1720.
Finalmente, o beltrano mais antigo indicado no Houaiss é de 1890, mas eu encontrei vários a partir de 1822:
[…] donde lhes veio o conhecimento de que em fulano e sicrano, melhor de em beltrano, se reunem essas relevantes qualidades e condições?
“Portugal—Continuação do Juizo sobre o Decreto das Eleições”, O Conciliador, Maranhão, 13 de Novembro de 1822, p. 1.