Try a small sample job on some scrap of the same material. It is the only way you will know for sure.
Myself, I have used stain, Gel stain, acrylic paint, and spray paint over shellac, and over wipe-on oil base poly. The drying times were different, the ease of application varied, but the final results have seemed the same. Only caveat is to make sure whatever you use is thoroughly dried before applying the next coat. I usually allow twice what the container says.
I prefer to apply an initial coat or three of sealer, sanded smooth, before cutting, Makes it easier to remove the excess fill color. Sometimes I even wax the surface with caranuba car wax. It gets removed when I sand the excess coloring off.
For PhotoVCarve halftone portraits, I usually use maple substrate, and dark brown stain (or paint) . A sealer after carving helps prevent bleeding.
My choice of what to use often is whichever I reach first on my paint shelf. I can't give you any information as to the life of the various options, but would suggest a final coat or 2 of a Poly finish would be a good idea. (I'm partial to Wipe-On Poly because I can apply it with a piece of paper towel, which I can just throw away after it dries.)
Good judgement comes from experience.
Experience comes from bad judgement.