palace – дворец

palace (n.) (резиденция императора, короля, архиепископа); из старофранцузского «palais» - дворец, двор; из среднелатинского «palacium» - дворец; из латинского «palatium» - холм Палатин, холм дворцов; из гора Палатин, один из семи холмов древнего Рима, где стоял дом императора Августа, позже – резиденция Нерона
early 13c., "official residence of an emperor, king, archbishop, etc.," from Old French palais "palace, court," from Medieval Latin palacium "a palace" (source of Spanish palacio, Italian palazzo), from Latin palatium "the Palatine hill," in plural, "a palace," from Mons Palatinus "the Palatine Hill," one of the seven hills of ancient Rome, where Augustus Caesar's house stood (the original "palace"), later the site of the splendid residence built by Nero.

Опять сказочные персонажи участвуют в этимологии.

1675:
The PALATE (palait, F., palatum, L.) – нёбо
Тоже от римских императоров?

В основе «полати»
Полати Толковый словарь Ефремовой
мн. устар. 1) Широкие нары, располагавшиеся в избах под потолком между печью и противоположной ей стеной, на которых спали. 2) Деревянный помост в церкви на уровне 2-го этажа; хоры.

В основе – положу, положить, - ложе, лежу. Затем – палата; другой подход – пала, палка

Палата Словарь иностранных слов
(от лат. palatium - дворец). 1) великолепное здание. 2) название некоторых присутственных мест в России. 3) во Франции и Англии: часть парламента.
(Источник: "Словарь иностранных слов, вошедших в состав русского языка". Чудинов А.Н., 1910)

1828:
PALATIUM, PALLATIUM – холм Палатин, один из семи римских холмов; из φαλλάντιον, пишет Скалигер; так греки называли высокие холмы. Исл. “fiall” – гора (не удивительно, вулканы же, пал). Teuton. “phala” – деревянный замок; этрусское «falantum» - небеса (этрусское же не читается?!); Germ. “pfalz” – дворец; Sax. “palast”; Welsh “palas, plas”; Cornish “place, plas”; Teut. et Sueth “falu” – мужской член; Goth. “fala”

Т.е. все свелось к пале, палке. Возможно, что и «палю», как и «polis», т.к. место расчищали посредством выжигания, - корчевать, - себе дороже. На Палатине – сосны (пинии), пока корни вытащишь.