So what is the difference between complex and complicated? Is there one?
The answer is that their meanings overlap. The main dictionaries in the US and UK (Oxford, Merriam-Webster, etc.) define complex using the word complicated, so the adjective complex means made up of many different parts, or complicated. Complicated means consisting of many interconnecting parts, or intricate. So very similar.
The noun complication moves on to describe something that makes something complicated, a complex state (there we go again) and in medical terminology, a disease or condition that is secondary to the main one but makes it worse.
Complex as a noun can mean a few more things – an interlinked system (the military-industrial complex), and then Oxford links but Merriam-Webster lists separately, a group of interlinked buildings. It also has a meaning in psychology of a group of emotionally significant but repressed ideas which cause an abnormal kind of behaviour or an abnormal state (a persecution complex), and by extension, a more pop-psych preoccupation or exaggerated reaction (I have a complex about spiders). There’s a chemical meaning to do with connections, too.
So the nouns vary, but if you’re describing something made up of lots of different things that might be a bit confusing or intricate, it can be complicated OR complex.
Having done some rooting about, I did discover this Washington Post resource claiming to delineate a difference.