Существительное поднебеса (?), от которого, вероятно, Вы и образовали форму с поднебес, в лексической системе русского языка отсутствует. Правильно: из поднебесья.
Общеупотребительно и стилистически нейтрально: батон колбасы, сочетание палка колбасы разговорное. Эти примеры также приводят, когда говорят о различии в речи москвичей и петербуржцев. Москвичи говорят батон колбасы, петербуржцы – палка. См. также интересное обсуждение на форуме Lingvo.
Правильно: батон колбасы.
Между этими словами нет родственной связи. Слово кат "палач" пришло в русский язык в эпоху Петра Первого, заимствовано из польского языка, восходит к древневерхненемецкому Gatte – "помощник палача".
Батон колбасы – корректно. Одно из значений слова батон – 'о пищевом продукте вытянутой формы'. В разговорной речи возможно и палка колбасы. См. также ответ на вопрос № 246955.
Правильно: Не знаю, сумел бы я спастись, если бы не палка.
Мужские фамилии склоняются: нет Лысака, Бабака, Гасака и т. д.
1. На собственные наименования правила правописания распространяются ограниченно, поэтому правильное название отеля - такое, как в официальных документах. Наиболее логично написание "Атриум-палас-отель".
2. Верно: Спас на Крови (название храма).