First of all, 라고 in 아니라고 is what we call a quoting suffix. It is different from the -고 coming at the end of a verb.
There are -라고, -다고 (and even 하고 sometimes) for different types of quoting someone else's speech.
1 그는 '싫어'라고 말했다. 그는 '이거다'라고 말했다 - 라고 in direct quoting with quote marks.
2 그는 싫다고 말했다, 그는 간다고 (말)했다 - -다고 in indirect quoting for adjectives and verbs except 이다 and 아니다.
3 그는 이거라고 말했다, 그는 이게 아니라고 말했다 - -라고 in indirect quoting for 이다 and 아니다.
The -고 in these quoting forms are not the same as the -고 ending of general verbs. The former captures a remark as a clause like "that" in English, while the latter indicates a sequence of doing one thing and then another. We need to separate these two types of -고.
Now let's go back to your sentences.
- 그는 아니라고 고개를 저었습니다 = 그는 아니라고 (말하며) 고개를 저었습니다.
Strictly speaking, there should be 말하며 (-며 indicates doing something at the same time as another) to complete the meaning, but 말하며 is dropped most of the time because -라고/-다고 clearly indicates speech..
So the important point is that -고 in this sentence is not showing one thing happening first. 아니라고 말하다 and 고개를 젓다 are actually taking place at the same time.
- 그는 고개를 젓고 아니라고 했습니다.
In this case -고 indicates a sequence of shaking head and then saying no, so it is not logical (people don't act this way). If you say 고개를 저으며 아니라고 했습니다, it makes sense as it indicates a parallel action just like your original sentence. But the original is still better because it shows more clearly that the shaking of the head is to make a denial.