Again, it's just like asking "what if I try to not go to the shop yesterday, what would happen to the bread I'm eating?". Can you decide today to not do something yesterday? No. In the same way, a time traveler can't "choose" to modify the past - it's something that's already happened.
Of course, this does imply that the future is also set in stone, so in fact you can't choose to go the shop or not tomorrow any more than you can choose to have done so yesterday. This is not a paradox, it's just counter to our subjective experience.
The way this particular idea of time travel works is like this:
1. A time traveler throws a grenade, killing Joan of Arc.
2. History happens.
3. The time traveler who killed Joan of Arc is born.
4. The time traveler goes back in time and kills Joan of Arc.
5. We hear of this event.
If we are looking at this when at time 5, do we find it surprising that it happened? Do we need any explanation? We can ask "what would have happened if the time traveler had instead killed Chairman Mao?", and we can get into a discussion on the possible future life of Joan of Arc etc. But since the event has already happened, we don't need a fundamental explanation for "why didn't it go differently", "what stopped the time traveler from doing differently" etc.
If you then accept that the future is just like the past - it is already decided - then the same banality happens if we learn of this event at time 3. We can ask "I wonder what would happen if this child wouldn't one day kill Joan of Arc", but it is simple musing about alternative histories, like asking "I wonder what would have happened if Hitler hadn't killed himself". The fact is that Hitler did kill himself, and that the child will kill Joan of Arc.
If you imagine the future as changeable, or if you imagine that beings can choose what they will do, then the paradox arises. But if you consider the future as set in stone, and if you consider that humans can't chose to do one way or another, than there is no paradox: history COULD have been different, but it just isn't. The same thing that stops you from changing the past also stops you from changing the future.
Note: I am not claiming that this view is "correct". Just that, if you accept it, than time travel really doesn't give rise to any paradox.
Just as much, if you have a time machine, and go to the past, you will do exactly what you had already done in the past. It is not something you have a choice on, it is simply a consequence of the universe so far. The same would be true if you went to the future - all your future actions were decided the moment you were born, the moment the Earth formed, the moment the universe was formed. There is no choice.
I myself can't entirely believe this notion of a fully deterministic universe. Especially one that doesn't even involve randomness (though randomness by itself wouldn't bring in any possibility of choice).
1. You start your day normally
2. You meet yourself from the future and discuss some niceties.
3. Many years later, you enter a time machine, and you arrive back at time 2, where you have that conversation with yourself that you remember.
The past has already happened, so it can't change. So, if you haven't met a time traveler so far, that is proof that no one will ever time travel to the moment and place where you just were, even if time travel becomes possible in the future.
Now, you may ask, 'what happens if at step 3 I decide to shoot myself, or not have that conversation?'. Here the answer is simple : that question makes no sense. You have already done our not fine these things, there is no power of decision that could influence this. It's like asking "what if I now decide that yesterday I didn't go to the store". The fact that the event at time 2 happened is fixed both in the past and the future. It was in fact fixed at the time of the universe's creation.
Now, you may not accept determinism, or you may believe in free will, and there are good reasons for both (quantum indeterminism, subjective experience, etc.). In either case, I don't think you can believe in time travel, since all of the paradoxes reappear. But if you believe the past and the future are already set in stone, there is no paradox if the two cross each other in certain ways. But it doesn't make sense about what you 'will decide to do', because this is as fixed as what you ate yesterday.