You use new a lot in the code to handle the dynamic construction of the FSM. Any chance to consider a templated, OO based approach with everything of static size ?
also as you are targeting small micro-controllers, on top of const char * for the name, support as well the F() macro so that I could do
State* stCall = fsm.addState(F("Call semaphore"), onEnter, onExit);
(it would mean supporting const __FlashStringHelper * and it would also affect getStateName()`)