C++ async is unfortunately a "bring your own runtime" sort of model (for now), but it does handle the part that would be incredibly tedious by hand, building above mentioned state machine.
Delegating the runtime nerfs many of the benefits that async can offer. If you are going to delegate the runtime it offers relatively little compared to just using threads.
So anyone that has experience in such model, including the awaitable magic methods, can grasp it.
While not cost free, the optimisers are expected to elide the cost most of the time.
Heap allocation is not required, just the default.
You can do static allocation if you wish, though it is a little more complicated than typical static allocation due to the relative unpredictability.
No, the std::mutex is the reason you have a condition variable. Never mix std::atomic with std::mutex-and-friends, you are very likely introducing race conditions that way.