It's sometimes what you don't see that is important. The link for grobotronics step down converter has a lot of specification info. Where is the line regulation spec? How does it react to the input voltage stepping?
I can answer that: too much to reliably power an Arduino.
Solutions? Well, if you are not using all those amps that the down converter is able to supply (It seems to spec 2.5, 3 and 4 amps...which one is right??!),
I would attack the input to the step down converter first. It's quite possible you need better filtering from the car's DC to the input of the converter. Nip the problem at the source, not after it's stepped down.
Filters on the output of the converter could degrade the load regulation ability.
alek_t's suggestion to add smaller (ceramic) caps would be a quick band-aid. I would try at least 0.1uF to 1uF. I would also consider adding another stage of inductor/capacitor to see if that works.
Smaller and cheaper might be to add an RC filter which can work wonders - IF you are not drawing a lot of current. Since you are stepping down from 12 to 5, you have at least 7 volts to work with,
so maybe a resistor that gives a drop of maybe 2 volts combined with another large electrolytic capacitor. The normal 2/i = resistor ohms formula should work. For power rating, I'd use 2*ohms*i^2 = resistor watts.
If you have an inductor, that might work well too, but finding a very low resistance inductor may not work noticeably better since resistance here would help the filter.