1929: "Paradox", a novelette by Charles Cloukey, mentioned on p. 286 of Paul J. Nahin's book Time Machines: Time Travel in Physics, Metaphysics, and Science Fiction, Second Edition; originally published in Amazing Stories Quarterly, Summer 1929, available at the Internet Archive; reprinted in Amazing Stories, September 1968, also available at the Internet Archive.
In the following excerpt a character discusses various paradoxical aspects of time travel, including the grandfather paradox:
"Gentlemen, I am going to omit details. It is becoming late and there is another part of this story I want to tell. Suffice it to say that I was transported into the past farther than I had come into the future! I placed the manuscript in the doctor's mail box. But before I did this I had to walk a mile, for I had arrived that far away from his house. While I was walking, my mind
cleared. Because this manuscript had been found by the doctor, I reasoned, I had been able to go to 2930. But also, only because I had gone to 2930 had the manuscript come into being. Which was the cause and which was the effect? That is a paradox I cannot explain. A thousand years from now it will be understandable and common to the people of the world.
"I started reasoning along another line. Suppose I should have traveled into the past to the time when my grandfather had been a little boy. If I were so inclined, I could kill my grandfather before he had had a chance to meet my grandmother, thereby depriving myself of the privilege of being born! But the fact that I was present to kill my unfortunate grandfather would show that I had been born. Therefore, I could not have killed my grandfather. It was hopeless.
"The most intelligent man in the world in 1428 could have proven to his entire satisfaction that such a thing as radio was scientifically and logically impossible; yet we have radio to-day. I actually convinced myself that time-traveling was logically and scientifically nothing but the utterest nonsensical paradox; yet I delivered the manuscript as per Bonn’s instructions.
"Then, still following instructions, I returned to the exact point at which I had arrived from the year 2930. As I returned I wondered what would have happened if I had thrown the manuscript into the river, instead of putting it in the mail box. Hawkinson, next morning, would never have found it, and therefore could never have sent me into the future. But unless he had found it and sent me into the future, I could never have had the manuscript to throw into the river. However, I seemed to think that throwing the manuscript into the river would be deliberately cheating fate. So I had delivered it.
"Later, when my life was at stake, I deliberately did cheat fate. That's why I’m here now. My death was scheduled for yesterday. I’ll explain that later on.
"I stood near the river, ready to follow Bonn's final instructions. I was to press a button in the belt that helped to support the complex improved time-machine on my back. I was ready to return to Bonn and tell him that the experiment was a success, that his invention had functioned as well in sending me back through the fourth dimension as the other had in sending me into the future.
I was ready to return to Dwar Bonn. But suddenly I hesitated. Why should I go back into the future? Nothing compelled me to comply with Bonn's request. I had
not even promised him to return. He had taken it for granted that I would. If it had not been for that aversion I then had for the thought of cheating fate, I think that then and there, I would have taken off the portable
machine and thrown it into the river.
"Another thought occurred to me. The night before Hawkinson had called me on the phone I had been sleeping peacefully in my Lansdowne apartment. Undoubtedly
I was sleeping there peacefully that very second, for I had traveled back through time to that same night. Then, if I should throw the machine into the river, there was nothing in the world to stop me from going over to Lansdowne and waking myself up. The idea fascinated me. It occurred to me that I would have a hard time convincing myself that I was I. Suddenly I started again. It was a scientific impossibility for a man to be in two places at the same time. But I was.
"Another paradox. I then determined that I should return to 2930 and have Dwar Bonn explain things to me. So I pressed the button in my belt. The 7.6 grams of 'solid electricity' in the generator of the outfit on my back was changed from matter into energy, producing a powerful current, which was transformed into what Bonn always called the NN-4 wave by the apparatus on my back, and I rose through the fourth dimension once more. I found Bonn smiling as I suddenly appeared in the laboratory, hardly a foot from the point from which I had started.
" 'It is a success,' he said. 'You've been gone thirteen seconds!'
"A short while later I requested him to explain to me the seeming paradoxes connected with time-traveling. And he did! He explained them fully. He explained
them logically and painstakingly. He explained them as simply as he could, but the cold fact remained that my brain was a thousand years behind his. (I defy any
scientist of to-day to write an explanation of the talking movies that would be understandable to a man living in the tenth century.) Bonn finally decided to stop trying. He told me that if I decided to remain in that era of time, he would arrange for me to be hypnotically educated by machines built for that purpose, though my brain would probably not be capable even then of comprehending the abstruse science behind that seeming paradox. For a long time I puzzled over myself and the hypothetical murder of my innocent grandfather, but it remained, and remains yet, an endless circle to me.