Quote from the paper:
"... a complex system cannot be beneficially described in this naive fashion [state machines], because of the unmanageable, exponentially growing multitude of states, all of which have to be arranged in a ‘flat’ unstratified fashion, resulting in an unstructured, unrealistic, and chaotic state diagram. To be useful, a state/event approach must be modular, hierarchical and well-structured. It must also solve the exponential blow-up problem by somehow relaxing the requirement that all combinations of states have to be represented explicitly."
So regular state machines are usable up to only a few states and transitions. Implementing the whole set of Statecharts features is far from the quick exercise of building an ad-hoc, implicit state machine. Fully using Statecharts introduces some overhead. But the true power of Statecharts shows when using hierarchy, parallel states, history and so on, things that build on top of state machines and take a bit more investment to learn how to use.
--
Another interesting aspect is the "formal semantics". Quote:
"The statechart formalism turns out to be quite a challenge when it comes to providing formal semantics ... The main difficulty is not in the depth of states or the orthogonality constructs themselves; ... The more difficult problems arise with the introduction of events and conditions that are generated within the statechart itself, and are sensed in orthogonal components."
So the idea is that given the same Statechart diagrams, two different implementations should end up in the same states when subjected with the very same sequence of events.
Perhaps this is less of a problem to build GUIs and other applications that don't have super stringent requirements on safety and verifiability.