So what? They're under water. If anything that makes it easier to alter their environment with lasting effects. In calm waters, it would be trivial to dig trenches and stack rocks, to create structures, as hunting traps or dens.

Either way, the octopus is similarly prehistoric, despite readily prehensile appendages.

Nor does a lack of hands readily explain the level of elephant intelligence, given a prehensile trunk.