Hola navaismo, no creo que la interferencia entre por los relay's, si no por el cable del sensor.
aitopes te recomendaría que useces un cable tal que los 2 que necesitas para la alimentación y transmicion de señal del sensor vallan entrelazados, o trenzados por así decirlo, esto es cuando ambos cables van haciendo giros sobre si mismos, estos giros cuantos más sean por unidad de distancia mejor es.
Aparte de lo anterior ese cable debería ser mallado, pero la malla solo se conecta a la PCB y no al sensor, por lo tanto del lado del sensor la malla queda al "aire".
Más alla del cable mencionado, supongo que el circuito está instalado dentro de un gabinete metálico y este conectado a la masa de la PCB.
Y el condensador que mencionas más arriba no va solo, si no que va en serie con una resistencia de 100 ohm 1W, ya que el capacitor solo se freiría si la tensión es de 220Vca.
Y para ir culminando puedes colocar un varistor de 250V a cada relay, para de esta manera reducir considerablemente las espureas.
Espero te sea de ayuda, un saludo.
Atte. CARLOS.