The paradox only appears because he treated space as a single dimension rather than an euclidean distance of arbitrary direction in multiple space dimensions. There is no need for the message to go back in time, thus no paradox to begin with. I don't go back in time when walking backwards, which is the same principle at a different scale.
The light speed limitation means that you can traverse one node in time or space at a time. Because we observe natural distance as euclidean, we can conclude that timespace has a randomized structure.