It's tempting to think one can come up with objective measures of musical complexity, but the problem is the number of dimensions musical complexity exists in:
Many people who listen to classical (in the more general sense of the word that encompasses baroque and romantic eras as well) dislike folk music as being too simple. They are listening to harmonic complexity - the changing of chords over time. Irish music usually has two or three chords repeated in a predictable pattern. But it has micro complexity - subtleties of emphasis, timing, melodic variation, grace notes, etc. - that make it, to my mind, far more complex than it is given credit for. These intricacies are particularly difficult to measure objectively.
Other kinds of music, like EDM, rap, etc. have rhythmic complexity. Fans of this music often think classical music is boring because classical tends to be rhythmically predictable.
Within classical music, there is Classical (Mozart era), which values balanced form, strictly following structures like AABA, with the complexity hiding within the endings and transitions between repeated sections.
This is very different from baroque (Bach, etc.), which often has rambling forms, and lots of micro complexity - dazzling changes of chords and keys, very intricate harmonies.
I won't even go into modern "serious" music, which stretches the definition of music to its breaking point.
The point being, there are as many forms of complexity possible as there are variables you can control in creating a piece of music.
I suspect this actually brushes up on fundamental limits of measuring complexity such as the Halting Problem in a currently only vaguely defined sense.
Edit:
To give a more direct listing of variables an algorithm might want to attempt to measure complexity in, off the top of my head, we have:
Chords, melody, polyphany, timbre, phrase structure, rhythm, rubato, dynamics, movement/song structure, whole piece/album structure, rhyme scheme, assonance, alliteration, onomatopoeia, vocabulary size, word repetition, references to other musical or verbal phrases in other works...
I mean, people get PHDs in analyzing this stuff.
Edit again:
Here's one really specific example that highlights both the fun and difficulty of doing this stuff algorithmically: there's a piece Bach wrote where one person reads the page right side up, and the other reads it upside down (starting from the other end, all notes inverted), and it works out. Noticing patterns like that would take a highly sophisticated algorithm akin to what is used to analyze genetic sequences.