Разумеется, Excel прекрасно поддерживает русский язык. Вот только работает он на старой, как экскремент мамонта, операционной системе Виндоус, где до сих пор стандартной считается кодировка 1251. И думает, что данные всегда лежат в ней.
Плюс формируете вы не xls, а HTML, замаскированный под xls.
И из-за этой маскировки Excel не предлагает поменять кодировку при импорте.
Поэтому есть два пути
1. Сохранять данные как CSV. Тогда при импорте можно будет выбрать кодировку.
2. Перекодировать данные перед сохранением,
mb_convert_encoding($output, "windows-1251", "utf-8");