En el idioma español, el uso de los dos puntos (:) en general viene a decir algo así como "por favor, presta atención a lo que voy a decir a continuación". Si seguimos esta idea general, parece lógico que en los encabezamientos de las cartas comencemos con algo así:
Estimado señor don Fulano [preste atención a lo que viene ahora que le interesa]
Y establezcamos esa idea de "preste atención" con los dos puntos:
Estimado señor don Fulano:
La propia RAE dice en el DPD que en algunas ocasiones los dos puntos se pueden sustituir por la coma, pero añade:
La diferencia entre el uso de uno u otro signo está en que con la coma el énfasis desaparece y la expectación creada en el lector con respecto a lo que se va a decir es menor.
Y desde luego, cuando nos dirigimos a una persona queremos captar su atención sobre lo que vamos a escribir a continuación en la carta. Sin embargo, dice la Fundeu que "cuando el encabezamiento consiste en una frase autoconclusiva, hay quien evita los dos puntos y los sustituye por punto". Sería el caso de comenzar una carta sin dirigirse a nadie en concreto:
Buenos días.
Esto no siempre fue así. Antiguamente los signos de puntuación simplemente representaban pausas de mayor y menor grado, como se puede leer en la Ortografía de la lengua castellana de 1815:
Fuera de aquella pausa casi imperceptible con que se separa una palabra de otra [...], se conocen otras cuatro que aumentan en progresión, y se indican con cuatro diversos caractéres: la menos con la coma, que se hace así (,): la que sigue á esta con punto y coma de este modo (;): otra algo mayor con dos puntos en esta forma (:); y últimamente la mayor de todas con el punto final, que en las locuciones ordinarias se hace así (.).
Es decir, que por entonces no tenía la connotación de "por favor, preste atención", sino que era un elemento separador como la coma o el punto y coma. Fíjate además que en el texto que acabo de transcribir se hace uso de los dos puntos para separar los elementos de la enumeración, cosa que hoy día no se hace.
¿Y cómo se introducían entonces las cartas? Usando el punto o la coma. Fíjate en el prólogo de la Gramática de la lengua castellana de 1771:

O en el prólogo de la primera edición del Quijote:

En las ediciones modernas se suele escribir "desocupado lector:", dado que Cervantes se estaba dirigiendo al lector tratando de captar su atención, como si fuera el inicio de una carta. Sin embargo, el texto original usa una coma, al no existir entonces la figura de los dos puntos con el mismo uso que hoy. En todo caso, estoy buscando en el CORDE y textos del siglo XVI escritos en formato carta sí parecen usar los dos puntos, pero no sé si es por cosa de la transcripción, dado que no puedo ver los originales. Buscando en Google encuentro algunas, y me llama la atención por ejemplo esta:

En esta imagen podemos ver que el encabezado no va seguido de signo de puntuación alguno, sino que se destaca arriba y centrado (como en el caso de la Gramática).