I think that UML is best considered for its complexity part by part, since mixing it all up, like class models, state machines etc, would create quite a monster that could express nearly anything anyhow, in ways that no one is really able to trace. Moreover UML is practically applied part by part and thus complexity considerations should follow this I order to head towards practically relevant results.
So, what more do we know when we know the complexity of a certain part of UML?
For example, in the case of a state machine the correspondence to complexity classes is rather obvious. There one can immediately see that, if its model employs a History Element “H” the implementation language requires a correspondingly higher expressiveness. Thus one can take this into consideration, when e.g. choosing a suitable Issue tracking tool for implementing the state flow.
In the case of class diagrams one employment of inheritance implies a certain minimal level of complexity*, thus one could immediately see, since this level cannot be checked by running tests on the application alone, one has to carry out code reviews in order to verify the application comprehensively.
Thus, I believe that applying complexity classes to UML can provide a substantial benefit, if it can support the controlled (complexity aware) use of language, i.e. if one decides the application to cover a higher complexity, one is immediately aware of the higher implementation cost. Finally, complexity awareness is cost awareness.
Comments very welcome.