You have to consider ground interference too, not only positive supply one.
For the relays use freewheeling diodes in parallel on the coil (1N400X will do in most cases).

For the motor, if not changing rotation, you can also put the same diode + 100n in parallel to the motor. Also 1n-10n from each motor terminal (but directly soldered on the motor terminals) to the motor case, which you ground it. If it changes direction, you skip the diode.

All connections to ground should be star-type. One wire from the motor (power circuit), one wire from the Arduino, one wire from the LEDs (even more needed if you PWM the LEDs for brightness dim), all meeting in a single common point. If Arduino gets reset when starting motor or switching relays, put another 1-10uF from its Vdd to ground.
Use a big capacitor of minimum 1-2mF on the main power supply (12V maybe you have), but do not be shy to add even more. If you use a 12V battery as a power source, or as back-up to a mains powered supply, no need to add capacitance more than needed by the voltage regulators.
Make all connections clean and short. Do not daisy chain to transfer the noise from one circuit to another (mainly to the Arduino). If you have a common power supply (so common ground), it is useless to use opto-couplers to drive the BD139. It will do no isolation, the noise will travel freely via the ground.