¿Que pasos legales he de dar para añadir un nuevo nombre al que ya tengo?

En primer lugar, tú, como ciudadano español, tienes derecho a cambiar de nombre o a añadir un nombre al que ya tienes en este momento siempre que concurra justa causa y no perjudiques a tercero.
Mi consejo es, ya que de todos modos, vas a tener que hacerlo antes o después, que te acerques al Registro Civil de tu localidad y le preguntes al funcionari ode turno, que se dedica a estos asuntos cada día y te informará "sobre el terreno" y seguramente mejor que yo.
Ahora te voy a explicar qué es lo que tienes que hacer, insistiendo no obstante en que vayas al Registro Civil porque tal vez tengan una instancia para este tipo de asuntos y te sea más fácil. Básicamente tienes que enviar una solicitud o instancia, dirigida al Juez encargado del Registro Civil de tu domicilio, en la que expresarás tus datos personales (nombre y apellidos, DNI y domicilio), acompañándolos de las pruebas pertinentes (fotocopia compulsada del DNI y fotocopia compulsada de la inscripción de tu nacimiento e incluso la certificación de tu bautismo si la tienes, como bien dices -para certificar que el nombre que das es tu nombre verdadero-). Te compulsarán estos dos documentos en el mismo Registro.
Cuando hablas de la necesidad de aportar dos testigos te estás refiriendo a otra cosa. Los dos testigos sólo son necesarios cuando tú tienes un nombre pero habitualmente utilizas otro y todos te conocen por este último nombre. Entonces estos testigos dicen que es cierto que todo el mundo te llama de otra manera distinta a lo que pone tu DNI. Por lo que cuentas no es este tu problema, así que nada. Otra cosa es que decidas llevar algún testigo que diga que efectivamente tu nombre actual te causa problemas de cualquier índole.
En la instancia deberás fijar claramente cuál es tu pretensión (qué quieres) y en base a qué fundamentos de Derecho lo haces. Es decir, debes explicar que quieres cambiar tu nombre actual por otro diferente (o añadir un nombre simple al que ya tienes) porque te causa problemas ya que te llegan cartas que no son para ti realmente, por motivos psicológicos, etc. Es necesario, eso sí, que pruebes ese perjuicio, cosa que puedes hacer con un certificado de un psicólogo que diga que efectivamente sufres por este motivo, por ejemplo.
En cualquier caso, los jueces suelen ser muy permisivos en este tipo de casos en cuanto ven que el nombre actual perjudica al interesado.
Creo que no me dejo nada. Si tienes más dudas pregúntamelas. Y aunque suene ha pesado, insisto en que lo mejor que puedes hacer es acercarte al Registro para que te informen, que al fin y al cabo están para eso.