Unfortunately for the supercomputing bacteria, worshipers build things that the worshipers think is useful, not what the god itself wants. Even specific orders, like Yahweh commanding the ark of the covenant or the Temple of Solomon ends up more "inspiring" their charge the right direction, not providing detailed plans.
So, without tools, what would semi-intelligent cuttlefish and octopi make for their gods?
Ink clouds and structures of mucus.
First off, they don't have tools, so they'll need to figure something out without being able to build things with tooling. They would be thinking of things useful to them... while also constructing things which bring themselves pleasure (because most temples are designed to wow their followers as well).
Ink clouds, shaped into specific forms as they dissipate would be a beautiful, if pointless to their gods, form of worship; the brain's own "numinous" circuits would reward the animals for producing these beautiful forms.
Structures of mucus, however, would be way more useful to the bacteria in building films and other organized structures. They could manipulate the religious sensibilities of the critters to make the macro-structures in the form they require, while handling the lower level stuff themselves.