Your middle example is only marginally grammatical, if at all.
The reason is that the gerund makes the action progressive, and this is only needed once.
"starting to do" is a progressive action.
"start doing" is also progressive.
"starting doing" is a kind of "double progressive" which doesn't make sense.
However, it is not a general rule that gerunds do not combine. For instance
Starting running again after not doing it for several years can be difficult.
This is different because "running" basically serves as a noun here, referring to an activity. Contrast with:
My nose is starting {* running | to run }.
Here, running is not a noun referring to an exercise activity, but the a verb denoting moisture coming out of one's nose.