Почему логотип съезжает в право при уменьшении масштаба от 100% и меньше начинает ехать?

Сборная солянка какая то. Позиционирование, флоаты, маргины отрицательные почти на 1000px и процентный маргин. Тут всё в корне неверно и работать адекватно вряд ли будет. Нужна демонстрация блока в онлайн редакторе как минимум.

Как можно добавить иконки к выпадающему списку?

Можно же просто на дивах сделать. Либо добавить функцию.
$('option').each(function () {
$(this).text("Sort by: " + $(this).text());
});

Как выровнять div по заданной позиции?

Дмитрий, Как насчёт задать невидимый блок который сдвинет текст? Вот так например. Либо задавать маргинами и просто менять рассположения на медиазапросах. Можно вообще сделать всплывающее меню для меньших экранов.