Начнем с леденца, с ним немного проще. Слово «леденец» неспроста так похоже на слово «лед». В чешском языке встречается глагол «ledovati», что значит «засахаривать». Когда первые леденцы попали в Россию, люди оценили, что они так же прозрачны и так же тают во рту, как и лед.
Почему ледяные сосульки сосать нельзя, а леденцы совсем не ледяные? Где логика?

Леденец

В словаре Даля указано, что «леденец» — это топленый сахар, в гранках или в слитках. А «ледянка» — мятная сахарная лепешка, которая холодит во рту.
Сосулька

С сосульками все немного сложнее. Ведь слово «сосулька» действительно связано с глаголом «сосать». Обратимся к нашему любимом словарю Даля, уж больно «вкусное» определение глаголу дал Владимир Иванович:
И добавляет, что «сосунок», или «сосунчик», — это тот, кто сосет, младенец, детеныш.
В славянских языках словом «сосать» называли кормление ребенка грудью. Раньше у детей не было сосок, и, когда мать уходила в поле, она заворачивала разжеванный кусочек хлеб в марлю или ткань и давала его младенцу. После «обсасывания» хлеб приобретал вытянутую или конусообразную форму. В одних говорах это изобретение называли «рожок», в других — «сосуля». А сколько младенцев эта сосуля погубила, став причиной удушья и инфекций.
Позже «сосулей» стали называть и другие предметы похожей формы.
Появились хлебные, пряничные и медовые сосульки. Человека, который обожал их есть, именовали «сосулечником».
В ярославских говорах «сосулей» называют вытянутый редис. Неудивительно, что по той же аналогии назвали висячую наледь на крышах.