What is complexity?
"Complexity" in this case is derived from the SEG algorithm, which is based on Shannon's information entropy.
This is not necessarily repeated regions, but regions in which a limited pool of characters are used (for example transmembrane regions, in which you are far more likely to see a hydrophobic residue than a polar one).
These scripts can help you calculate sequence complexity if you have specific examples in mind.
This idea asks how "compressible" is the information in the string of characters (think zip files).
Random characters in strings need more information, whereas less variable, more predictable regions can be recorded with less information and are less complex.
So a region in which you can more easily guess the next amino acid is simple, and more random amino acid sequences are complex. Sequences with more complexity are often more functionally important and more useful as functional indicators than low complexity sequences.
Indeed, BLAST used to mask low complexity regions as they were not useful for homology searches.
Why are complex regions more variable?
The question as I understand it is asking about this fourth conclusion from the paper.
Fourth, variation clusters occur in structurally well-defined and functionally important protein domains of high sequence complexity.
This is now not as paradoxical as it seems. Regions that are highly variable with lots more random/unpredictable amino acids such as those with well-defined structures and functions are more likely to occur in areas with high complexity as a result (which is a measure of randomness in a sequence).
There is more to this than meets the eye...
This is of course not the whole story.
In regions of high complexity, there are highly conserved and essential for life residues that cannot be changed.
On the other end of the scale, there are also areas like STRs that have low complexity yet are highly variable in length between individuals and underpin DNA fingerprinting.