Side effects are one type of complexity. You can make an indecipherable pure program too.
But is it maybe the difference between complicated, which indecipherable definitely is, and complex, in the sense of composed of many things?
You don't think a pure functional program can be composed of many things?
Right, a pure functional program can be composed of many things, so it can be complex even without side effects. Only a program with side effects is necessarily complex, as it includes at least two components if not more. Another interesting thought is that you can always encapsulate a purely functional program in a black box with an input and an output. Doing so with a program with side effects that themselves might be programs with side effects and their own interface is probably much more difficult.