It only has to be above the toilet if it's one that uses sea water...in which case the solenoid valve would be installed in the intake vented loop and has a different function: it's an air valve that closes when the flush button is pressed to allow the toilet pump to prime, opens when the flush button is released to break any siphon.
The solenoid valve on a toilet that's fed by pressurized fresh water the solenoid has an entirely different function. The flush water inlet line is tapped into the cold water line that feeds the head sink...the solenoid functions essentially the same way a faucet does...it opens to allow the flush water to flow into the toilet, closes to shut it off. That solenoid valve doesn't have to be above the toilet. So unless the builder
had a cockeyed idea that putting it below the sole would would improve the head decor by hiding some hose, it should be easy to get to...and under the vanity is a good place to look.
It's also possible that a PO removed it, thinking that the flush button is all that's needed to turn the flush water on and off...and it may be if he replaced the toilet with one has a built in vacuum breaks and water valves.
If your toilet needs one, and you can't find it above the sole, before I'd start taking up the floor I'd run a new flush water inlet line that tees into the cold water line under the vanity and put a new solenoid in it.