Да, эти названия склоняются, но не «теперь»: все подобные названия изначально были склоняемыми, и лишь относительно недавно распространился несклоняемый вариант. Подробнее см. в «Письмовнике».

Числительные два, три, четыре (а также составные числительные, оканчивающиеся на два, три, четыре, например двадцать два) в именительном падеже сочетаются с существительным в форме родительного падежа и единственного числа, например: двадцать два стола, тридцать три несчастья, пятьдесят четыре человека. Числительные пять, шесть, семь, восемь, девять и т. д. и составные числительные, оканчивающиеся на пять, шесть, семь, восемь и т. д., согласуются с существительным, стоящим в форме родительного падежа множественного числа, например: сорок восемь преступников. Однако в косвенных падежах согласование выравнивается: р. п. – двух столов, пяти столов, д. п. – двум столам, пяти столам.

Такая разница в согласовании числительных связана с историей русского языка. Названия чисел 5–9 были существительными женского рода и склонялись как, например, слово кость. Будучи существительными, эти названия управляли родительным падежом существительных, употреблявшихся, разумеется, в форме множественного числа. Отсюда такие сочетания, как пять коров, шесть столов (ср. сочетания с существительными: ножки столов, копыта коров) и т. п.

Сложнее обстояло дело с названиями чисел 2-4, которые были счетными прилагательными и согласовывались в роде, числе и падеже с существительными: три столы, четыре стены, три камене (ср.: красивые столы, высокие стены). При этом название числа 2 согласовывалось с существительными в особой форме двойственного числа (не единственного и не множественного; такая форма применялась для обозначения двух предметов): две стене, два стола, два ножа (не два столы, два ножи). К XVI веку в русском языке происходит разрушение категории двойственного числа, и формы типа два стола начинают восприниматься как родительный падеж единственного числа. Особая соотнесенность чисел 2, 3 и 4 (возможно, и грамматическая принадлежность к одному классу слов) повлияла на выравнивание форм словоизменения всех трех числовых наименований.

Вопрос о постановке/непостановке запятой в этикетной формуле С уважением(,) NN весьма непрост. Никакой грамматической необходимости в постановке этой запятой нет. Однако она ставится по традиции, заимствованной из образцов англоязычной переписки. Необходимость постановки какого-либо знака в этой фразе ощущается носителями русского языка интуитивно, поскольку она по сути представляет собой неполное предложение, которое может быть развернуто, например, так: С уважением относящийся к Вам NN (в позапрошлом веке она звучала более витиевато и представляла собой полное предложение: Примите уверение в моем совершеннейшем к Вам почтении. NN).
В ситуативно неполных предложениях (которые, кстати, становятся все более употребительными в современной разговорной речи) обычно на месте пропуска значимых членов предложения ставится тире. Однако, поскольку выражение типа "С уважением NN" применяется исключительно как этикетная формула эпистолярного стиля, традицией стало графическое отделение частей такого предложения, что вполне заменяет собой знак препинания (то есть тире, но не запятую, которой в этой конструкции нечего отделять или выделять). Можно перенести подпись на строчку ниже или разместить фразу слева, а Вашу подпись справа на странице, например:

С уважением
Екатерина Михайлова

См. в современных справочниках по делопроизводству или культуре письменной речи, например: Культура устной и письменной речи делового человека. Справочник-практикум. — М.: Флинта: Наука, 2000.

Порядок "Фамилия И. О." соблюдается при именовании адресата в деловых документах. В большинстве остальных случаев принят порядок "И. О. Фамилия". См.  ГОСТ Р 7.0.97-2016 "Национальный стандарт Российской Федерации. Система стандартов по информации, библиотечному и издательскому делу. Организационно-распорядительная документация. Требования к оформлению документов" (утв. Приказом Росстандарта от 08.12.2016 N 2004-ст) (ред. от 14.05.2018). 

1. Современные словари указывают на книжную окраску слова "протестант" в этом значении. При общей высокой стилистике такое словоупотребление корректно. 

2. Это дальнейшее (и вполне логичное) развитие следующего значения: "совокупность выразительных средств, раскрывающих тему, идею, мысль (фильма, направления в искусстве, школы). С. фильма. С. театральной постановки. С. абстракционизма".

Правильно: У него, то есть у меня, разболелась голова.

Конечно, простых правил нет. Законы словообразования подробно описываются в грамматиках (например, в «Русской грамматике» 1980 г.), кратко, обобщенно — в учебниках. Наши знания о словообразовании постоянно пополняются благодаря продолжающимся научным исследованиям. Узнать о современных словообразовательных связях между словами можно из словарей, прежде всего словообразовательных (см., например, список словарей здесь). В некоторых других словарях, например толковых, так же могут быть представлены сведения о словообразовании. Так, в «Большом толковом словаре русского языка» под ред. С. А. Кузнецова показано, что существительное недоедание образовано от глагола недоесть. 

В школе учат менять слово с безударным окончанием на слово с ударным окончанием (подставлять слово того же склонения), тем самым прояснится гласный в нужном падеже: в чистой тетрадке(?) - на чистой доске = в обоих случаях пишем букву Е.

Водитель и автоводитель - это разные лексемы (разные слова).