Muss ich dann alle + Leitungen an den Spannungswandler an dem ja der 12V Akku hängt, anschließen.
In erster Näherung ja. Aber wohlgemerkt an den 5V-Ausgang Deines Wandlers.
Und weiterhin würde ich noch etwas selektieren - die empfindlicheren und wenig stromfressenden Komponenten würde ich am Arduino lassen und nur die "Stromverbraucher" an die Wandler-5V.

Glaube nämlich nicht daß das von Dir beobachtete Phänomen auf die Schwäche der 9V-Batterie zurückzuführen ist. Da ist erstmal die "lumpige" Verdrahtung der Stromversorgung (= Experimentieraufbau mit vielen gesteckten, dünnen Kabeln - besonders bei der Masseführung) verantwortlich, denke ich.

Wenn Du Deine Arduino-5V von groben Stromfressern (LEDs, auch die Backlight-LEDs der LCDs) befreit hast kannst Du auch mal versuchen dem Arduino an der DC-Buchse direkt die Batterie-12V zu verfüttern aber dann gleich erstmal vorsichtig den Finger auf den Onboardregler um zu prüfen wie heiß der wird und ob man ihm das auf Dauer zumuten kann. Vorsichtig weil heiß werden wird's schon...

*Nur geschätzt*: Wenn der unter 50mA bleibt sollte er das schaffen, bei 100mA wird's schon sehr knapp und darüber laß es lieber sein.