Paelha é o aportuguesamento do prato espanhol paella – à base de arroz, carnes, marisco e legumes –, que, por sua vez, é uma designação com origem no valenciano (e catalão) (Dicionário da Real Academia Española). A forma paella também está atestada nos dicionários portugueses (ver Infopédia, por exemplo), mas, por se tratar da forma não portuguesa, deve ter o tratamento gráfico dado aos estrangeirismos: itálico ou entre aspas. 

Contudo, note-se que o prato espanhol deve o seu nome ao utensílio de cozinha onde se confeciona, também chamado paelha ou paella (frigideira com duas asas)¹. A designação deste instrumento, por sua vez, tem origem mais antiga que o prato em si, no latim patella, «espécie de prato grande de metal» (Dicionário Houaiss). Também, com a mesma origem, encontramos em francês poêle, «frigideira» (ibidem).

¹ Estamos perante uma sinédoque que se fixou na língua: o objeto é mencionado para nos referirmos ao seu conteúdo. 

N. E. (06/11/2022) – O dígrafo ll das ortografias espanhola, catalã e valenciana corresponde ao lh do português. Acrescente-se que, no valenciano e no catalão, a forma paella não é palavra patrimonial, isto é, não é palavra originária do latim vulgar que tenha passado diretamente aos dialetos catalães da Alta Idade Média. Na verdade, constitui um empréstimo do francês antigo paele, este, sim, evolução patrimonial do latim patella. No Diccionario Crítico Etimológico Castellano e Hispánico, no artigo que dedicam à palavra castelhana paila («vasilha grande redonda e pouco profunda»), Joan Coromines e José Antonio Pascual comentam igualmente a palavra paella (tradução com adapatações; para as definições do termos castelhanos, valencianos/catalães e franceses, consultou-se a Infopédia):

«[...] a forma paele ou payele, que é a etimológica [de paella], subsistiu em francês até ao século XV [...] e não só designava a frigideira ou sertã, mas também vários utensílios metálicos de maior tamanho, uma espécie de braseira, un bassin ["vasilha redonda e larga"]  ou bassinoire ["recipiente em que se deitavam brasas para aquecer a cama"] [...], e ainda um recipiente empregado para dar banho a uma criança [...], que deve ter sido muito semelhante a uma paila; ainda hoje o francês poêle tem, além da aceção mais conhecida, a de "recipiente para fundir o estanho", "caldeira para evaporação da água das salinas", "caldeirão para derreter sebo". A mudança de paele em paila pode ter-se produzido em castelhano; aliás, existe a variante paile [...], que é segundo Bloch [Oscar Bloch, Dictionnaire Étymologique de la Langue Française] a que serviu de intermediária fonética entre o antigo paele e a forma atual poêle. Em latim, a PATELLA servia para cozinhar ou servir alimentos e podia ser de metal ou loiça, mas também se empregava com outtras finalidades, em especial, de caráter litúrgico [...].

Em catalão, paralelamente ao castelhano, o vocábulo existe com duas formas, autóctone e tomada do francês: a primeira, padella, ainda se ouve nos Pirenéus (desde S. Juan de las Abadesas até ao Alto Pallars e a Ribagorza); à segunda, paella "frigideira, sertã", foi adaptada a terminação auóctone -ella, mas a palavra mostra a sua procedência forasteira por causa da queda do -d- intervocálico. [Paella é palavra] já antiga [...] e hoje está quase generalizada; daqui tomou o castelhano paella [...], termo especializado no sentido de "arroz à valenciana", assim chamado porque se confeciona numa frigideira mais ou menos grande.»