Da ist aber noch was oberfaul; CLK an Masse kann natürlich prellen und dabei steigende Flanken erzeugen. Trotzdem dürfen dann nicht Relais abfallen oder anziehen, es sei denn, Du hast die die Daten-Pegel / 8 Eingänge verändert.
Bei CLR nach Masse müssen alle Relais abfallen, weil dann überall Low an den Augängen ist (Reset-Zustand). Wenn das nicht so ist, dann ist der 273 im Elektronen-Himmel oder mit der 5V-Versorgung stimmt was nicht.
Du hast richtig gelesen, 100nF möglichst dicht an +5V und GND des 273, damit die (Um-) Schalt-Spitzen den Baustein nicht selber stören und Spitzen von woanders her abgefangen werden. Im 273 sind immerhin mehrere FlipFlops drin, und die reagieren ziemlich sauer auf Störspitzen.

Edit: Zwischen CLK und den Eingängen und zwischen CLR und den Eingängen zum 273 sollten gleiche Widerstands-Verhältnisse, sonst hast Du die PullUp's nicht nach +5 liegen (oder nicht alle). 4,7kOhm vom Eingang zum +5 und vom +5 mit 4,7kOhm zum CLK mach zusammen nicht ganz 10 kOhm !!!