Well, they can't be killed simultaneously if one is killed before the other - but if that were to happen: We would both be outside of normal time which would create some interesting problems. Both our grandfathers would be dead but as we are in existence it would mean that we would return to real time to find that although we exist, nothing we ever knew does (a bit like in "It's a Wonderful Life). However, I think it would be incredibly selfish of ಠ_ಠ to kill my grandfather when I am simply trying to resolve a paradox, especially as it was his idea to get the time machine in the first place
Yes. That's why it's called the Grandfather Paradox. We could experiment with the Great Uncle Twice Removed Paradox, but it is less well documented and the ramifications are unclear.