Presumiblemente hay un regulador entre el suministro de 12V y el arduino. Mientras la fuente de alimentación de 12 V permanezca lo suficientemente alta para que funcione el regulador, mantendrá constante la tensión del arduino.
Sin embargo, los reguladores no son perfectos. En particular, solo pueden compensar las variaciones de potencia de entrada hasta cierta frecuencia. El ruido por encima de eso se pasará a la salida. Si cree que la potencia de entrada puede ser lo suficientemente ruidosa como para que el regulador no pueda bloquearlo todo, coloque un pequeño filtro en la entrada del regulador. La mayoría de los reguladores funcionarán bien hasta unos 10s de KHz. No dijiste cuánta corriente consume el arduino, pero tienes mucho espacio para la tensión. Una resistencia de 10 ohmios solo bajará 1 V a 100 mA, lo que aún deja mucho para que funcione el regulador. A continuación, una tapa de cerámica de 10 uF a tierra justo en frente del regulador formará un filtro de paso bajo con una reducción de 1.6 KHz. Eso debería ser lo suficientemente bueno como para mantener la entrada del regulador a las frecuencias con las que puede lidiar.
Por supuesto, la mejor manera de manejar el ruido es no hacerlo en primer lugar. Es absolutamente necesario un diodo o algún tipo de amortiguador para atrapar el retroceso inductivo cuando el solenoide está apagado. La razón principal es evitar freír lo que está cambiando el solenoide, pero un efecto secundario será disminuir el ruido general.