Is there such a thing as an ultra low power solenoid?
It depends how much force you need. In general, you need quite a bit of current to run even a really tiny solenoid (hundreds of milliamps), and you need to hold that current to keep the solenoid pulled in or pushed out (depending on configuration). The force is proportional to the magnetic field, which is a product of the number of turns and current through the coil - so, you are usually looking at a fair bit of power to operate a solenoid. You could quite easily simulate this in FEMM if you're familiar with using that software.

There are other options for really small linear actuators than solenoids though. Many cameras use really really tiny stepper motors for adjusting lens focus. See this post for more details. I have seen these types of steppers available with leadscrews on AliExpress before. They will need high amounts of current to step, however, you only need to supply that in short bursts when actually stepping - so, you could charge up a big tantalum cap and dump it into the stepper windings at each step, and your average power consumption could still be down in the milliwatts. It wouldn't be fast, but if you're power-limited (such as from running off a coin cell battery or something) it should work.

Finally, there are electropermanent magnet actuators, which can be used as very low-power, very small bistable solenoids and stepper motors. An electropermanent magnet exploits the fact that AlNiCo permanent magnets are pretty easy to demagnetize, and NdFeB permanent magnets are very hard to demagnetize. The AlNiCo magnet is put into a magnetic circuit in series with the NdFeB magnet and ferrous keepers. Flipping the field direction of the AlNiCo magnet with a coil causes the field from the NdFeB magnet to be either confined to the circuit or forced to travel in the air, creating a "switchable" permanent magnet.

These are very cool when used as tiny actuators, but they aren't commonly available commercially, so you would have to build your own. Ara Knanian's PhD thesis is the best resource I've found for the theory and construction of these devices.