Now we are at a point where angels fear to tread...
I can't say what exactly the Start/EndUndo system is doing when not properly used in one level, but it definitely doesn't work in a way that supports nesting. Here I just tried a small modification of my previous scripts:
import c4d
def main():
    doc.StartUndo();
    obj = doc.GetFirstObject();
    doc.AddUndo(c4d.UNDOTYPE_CHANGE_SMALL, obj);
    obj.SetName("Renamed!");
    doc.StartUndo();
    obj = obj.GetNext();
    doc.AddUndo(c4d.UNDOTYPE_CHANGE_SMALL, obj);
    obj.SetName("Renamed!");
    doc.EndUndo();
    doc.StartUndo();
    obj = obj.GetNext();
    doc.AddUndo(c4d.UNDOTYPE_CHANGE_SMALL, obj);
    obj.SetName("Renamed!");
    doc.EndUndo();
    obj = obj.GetNext();
    doc.AddUndo(c4d.UNDOTYPE_CHANGE_SMALL, obj);
    obj.SetName("Renamed!");
    obj = obj.GetNext();
    doc.AddUndo(c4d.UNDOTYPE_CHANGE_SMALL, obj);
    obj.SetName("Renamed!");
    doc.EndUndo();
    c4d.EventAdd();
if __name__=='__main__':
    main()
I used the same sequence of five renames, but I nested rename 2+3 into a new Start/EndUndo without closing the outer first.
If you apply Ctrl-Z on that, you will find that the first Ctrl-Z reverses the last three renames (NOT just the last 2), one more Ctrl-Z reverses the second rename, and one more the first. That means that an undo step goes back to the last StartUndo (not EndUndo) that the programmer has set. Any nesting is ignored.
I did a few more nesting experiments but I'm not posting them here as they all point to the same behavior. I do not get any errors though, even if I completely botch the sequence - two StartUndo in a row, AddUndo before StartUndo, AddUndo after EndUndo... it actually still works, but with the little limitation that each StartUndo that I issue will break up the sequence and require a new Ctrl-Z to undo. (I am not going into full reverse engineering here now - it would be nice if the documentation could tell us how error cases and nesting are actually handled, though.)
That means that if you have commands that internally perform an Start/EndUndo, you will not be able to get out of the additional Ctrl-Z. Same, I guess, if you issue a StartUndo inside of a function that you wish to reuse (although that may be a problem more suitable for libraries).
You may argue that this is a design flaw. A nested Start/EndUndo could actually be treated like a single subcommand, with a Ctrl-Z working only on the highest level - which would revert the results of a functionality from the view of the outermost Start/EndUndo, while all nested Start/EndUndo pairs on lower levels do not affect the reversal (so you could use a CallCommand including its internal Undos without enforcing another Ctrl-Z in the end). I'm just not sure whether C4D could handle this conceptually, as it would be easy to lose yourself in a tree of Start/EndUndos throughout the program.
Anyway. Your best bet may actually be to skip the CallCommands if possible and perform the necessary change by yourself, so you have a better control over the Undo sequences.
Or you can issue a feature request for a CallCommand with an additional parameter that allows you to suppress the Start/EndUndos that are added internally.
 
 ). When the whole thing is easier to maintain as a Python tag in the end, I put it into the tag...
 ). When the whole thing is easier to maintain as a Python tag in the end, I put it into the tag...