Descargo de responsabilidad: en esta respuesta usaré señor para referirme tanto a señor como a señora. Igualmente, usaré don para tanto don como doña.
Históricamente, el tratamiento de señor presuponía nobleza, potestad o heroicidad, aunque ya en el siglo XVIII aparece recogido en el Autoridades con la acepción de que era usado como tratamiento para referirse a otras personas, ya sean iguales o incluso inferiores. En cambio, don siempre ha sido usado como expresión de cortesía y respeto, sin que este indique título alguno. Su uso hoy día implica simplemente que la persona ha alcanzado una cierta edad o estudios (aún recuerdo a mi abuelo diciéndome que ya se me podía decir "don Carlos" cuando cumplí los 18).
Pero ¿por qué uno se usa con el nombre y otro con el apellido? La Wikipedia dice:
En su uso original se anteponía solamente al nombre de pila o al nombre de pila seguido del apellido. Así, al distinguido Juan Esquer se le daba indistintamente el tratamiento de don Juan o don Juan Esquer. En el caso de usar sólo el apellido, el tratamiento correcto era el señor Esquer.
Dice también:
Se usa el título «señor» antepuesto al apellido, generalmente para expresar la condición de casado. Es así en expresiones como: «El señor y señora González».
Esto cuadra con su origen como título, puesto que los títulos se heredaban dentro de una familia, por lo que al final prevalecía el apellido familiar que era lo que se transmitía igualmente. El cambio el tratamiento don se usaba con las personas individuales, de las cuales el nombre era lo que realmente las distinguía. Y además no se transmitía, sino que cada individuo se lo tenía que ganar.
Se encuentran usos siguiendo esta misma pauta desde antiguo:
[...] e a pedimiento del dicho señor Velez e del dicho concejo e vecinos de Araia, fize escriuir este testimonio [...].
Anónimo, "Sentencia de pleito [Documentación medieval de la cuadrilla de Salvatierra]", 1455 (España).
Y desde más antiguo aún don , dado que se encuentran ejemplos ya en el siglo XI, en textos en latín:
Facta carta in manu don Lope, prioris Sancta Maria de Neguosa [...].
Anónimo, "Donación de fincas en Tafalla y Nicuesa [Documentos correspondientes al reinado de Sancho Ramírez]", 1094 (España).
Y en El Cid, de 1140, recordemos a "don Elvira e doña Sol".
Resumiendo: entiendo que esta diferencia en cuanto al origen de ambas palabras es la que marcó que una se usara con los apellidos (lo que se transmitía junto con el título en el caso de señor) o con el nombre (lo que distinguía a cada persona individual en el caso de don).
