Disturbed digital out at 4Mhz on Arduino NANO
This is not a limitation of the Arduino: you can toggle a pin on every clock cycle. It's a synchronization problem between the generated signal and the triggering of the scope. Your scope displays several traces superimposed, and it synchronizes them on the rising edges, but since those are unequally spaced, it gets out of sync with the full period of the signal. By adding a few nops you reached a lucky synchronization in your second version of the code.

The simplest solution is to set the scope mode to Single instead of Normal. Then it only displays a single trace and synchronization is not an issue anymore.

Another option would be to use one of the bits of PORTD as a trigger
signal. This bit should cycle only once inside the loop. PD5 should
work in the current version of your code. Configure the scope for
external trigger and feed this signal into its TRIG input.