Not sure if this can be regarded as a temporal paradox, but there is indeed a kinda major plot issue.
When Agent J is fighting Boris The Animal in Cape Canaveral, he shouts "Heey! Boris The Animal!" in order to startle Boris. He then runs in Boris' direction, grabbing him before jumping from the top of the Saturn V launch pad. You can see this scene here:
When Agent J activates the time travel device, the scene makes it seem like Boris The Animal is also going back in time along with him. Moments later, they are both back at the top of the launch pad, but Agent J remembers jumping while Boris doesn't. This suggests that Boris died in the fall.
Now, if we just go along and assume that only Agent J goes back in time, there remains a larger problem. Up to that moment in the movie, we've seen that the time travel device transports someone back in time, but does not care if the person already existed in the "time of destination". So, when Agent J finds himself back at the top of the platform, there should be two of him: the one who just time-travelled, and the one who was there before the travel. That's not what happens.
You can try watching this video - but there's a chance you might end up more confused, instead of less, so I recommend you try to bear with my explanation first:
Upon some rationalization, I developed an hypothesis which could explain this strange feat. We notice that Agent J spawns at exactly the same place than his (seconds-)earlier self was... at the grips of Boris the Animal. Perhaps there is a "bug" in the time-travel device that causes a person to "collapse" (like a wave function), should that happen. But this is just something I like to think about; it is not backed by the storywriters, as far as I know. As a bonus, this could also explain why he is not wound from the previous projectiles that Boris shoots at him.