I don't think there is a conflict between imperative thinking and state machines, but I do agree that lots of programming languages neither provide built-in features for expressing state machines nor support expressing them particularly elegantly, and that the superior support for general abstraction in certain functional languages reduce the friction of use.

It's pretty easy to imagine, though, a class based OOP language where each class was also an HSM, with methods defined per state and identifying transitions (as well as states and their entry and exit behavior being explicitly defined.)