Is autorotation possible from a 0 rpm start at high altitude?
Go back to Estes rocket days.  There is a whole class of competition rockets known as "heliroc" or helicopter recovery.  These ascend like a conventional rocket, in a vertical(ish) path and fin stabilized; at (or near) apogee, they release a rotor by some means and the rotor spontaneously begins to autorotate, often giving a lower descent rate than a parachute.

Go even further back: look at maple seeds (aka maple keys).  They autorotate so efficiently that they'll enter stable rotation and constant (low) sink rate in as little as one blade length of fall (they do have very low wing loading, however).

So, yes, it's possible for a rotor disk to spontaneously begin autorotation from a dead stopped starting condition.  Mother Nature does it billions of times every autumn, and school children do it thousands of times every year.

Yes, this will work with a coaxial rotor, if you can keep the rotors from interfering with one another during deployment (for instance, by braking them until fully deployed).  However, since there's no reaction torque from freewheeling, autorotating rotors, there's no reason to have coaxial rotors.  It's far simpler to use an ordinary rudder for yaw control than differential collective, and you'll have half as many parts for pitch and roll.