Hay posibilidades de hacerlo legal en España o tendría que crear la empresa en otro país como Estonia que están reguladas?
Creo que la parte legal no es tan compleja como la parte operativa del exchange ya que si quisieras podrías estar ubicado en españa pero basar tu exchange en leyes de otro pais. Como por ejemplo 'El Salvador' en donde Bitcoin se ha convertido en una moneda legal. Y para esto deberías de contactar con algun gestor en El salvador para que te ayude con el proceso legal en ese pais.
La parte compleja viene en el momento de la programación de la casa de cambio y la seguridad que necesitas para este, en el momento que hagas tu exchange público este se volvera un objetivo de los hackers, así que hay que manejarlo con cuidado.
Y el último obstáculo es el capital ya que necesitas tener un buen respaldo económico para empezar a operar.