Sure, but as soon as you create linkage between them - if the state of machine A affects what transitions are possible when in machine B and vice versa - then you don’t really have two state machines, you have a single Cartesian state machine combining both. Or you have a pair of metastatemachines which aren’t able to be analyzed in the same way as an independent state machine.

It’s like the difference between solving a maze, and solving a maze with constantly moving walls and traps in it.

Yes. From intuition I'd say that getting the right granularity is just as hard as getting other granularities right (e.g. how "micro" or "macro" your services should be).

In the end I don't pursue an absolute truth. Things are often gradients, one can pick whatever tone seems more reasonable.

This was my thought too, I hear most people get a bit jumpy when they see two state machines, like its too many moving parts.