There are many interesting answers to this question already, but none of them seem to answer the question exactly.

As @Duskwuff's answer says, there have indeed been stories of regrettable immortality for a very, very long time. However, as @Peter Pavlík points out, most if not all of these tend to be due to the type of immortality in question or a form of curse being tied to it, not the immortality itself.

TV Tropes

TV Tropes, as also referenced by @Duskwuff, lists the concept of undesired immortality as Who Wants to Live Forever?.

According to the examples from that page, the oldest example of ending an eternal existence being something to strive for probably comes from Buddhism. Since there it is due to life inherently being a form of pain and the only immortality involved is through reincarnation and actually the natural state of all life, this does not exactly fit yet.

Literature

The oldest example from the "Literature" section appears to be The Tale of Norna Gest, estimated 1300 AD.

When he was recently born, his father had invited three seeresses, or norns, to foretell the child’s future. Two of the norns made good prophecies, but the last one was in a bad mood and when some rude guests enraged her, she cursed Gest to live no longer than the candle that burned beside his cradle. So the other norns extinguished the candle and told Gest’s parents to keep it, and Gest gained immortality — he cannot die before the candle is used up.

On the wish of King Olaf, Norna-Gest agrees to be baptized. After a time, King Olaf asks him how long he plans to live. Norna-Gest says that he wants to die, being three hundred years old. In the presence of King Olaf, he lays down on a bed and lights the candle. A priest gives him the last rites. When the candle burns out, he dies.

This story at least involves a human being attaining immortality though unnatural means deciding to end his life voluntarily.

This seems to be by far the oldest example of a story like this.

The next oldest story I could find from TV Tropes is The Ring of Thoth by Arthur Conan Doyle, first published in 1890.

Mr. John Vansittart Smith is a student of Egyptology who travels to France to see some papyri in the Louvre Museum. Tired from his visit, he sits in a corner of the museum and dozed. When he wakes up, the museum is closed and he is locked inside. Trying to get out he meets a strange man who seems to perform a ritual on a mummy. The curious man tells his story: His name is Sosra and he was born 3500 years ago in Egypt. He was a priest of the god Osiris and discovered a remedy against death. He used it and shared it with his assistant, Parma. He wanted then to administer this elixir to his fiancee, Atma, but she died just before. He went desperate because he couldn't join her in the afterlife. So he wanted to become mortal again. Parma reported him that he had found an antidote but he had decided to use it for himself so he can die and meet Atma beyond. Sosra realized that the antidote was in the ring of Thott but Parma had hidden it and he took his secret to the grave. 3500 years later the mummy of Atma is found by French archaeologists and repatriated to the Louvre. Sosra succeed to be hired in the museum, found the Atma sarcophagus and got the ring containing the precious elixir. At the end of his incredible story Sosra accompanies Vansittart to the exit. Two days later he learns in the newspapers that a man was found dead in the museum entwined in the arms of a mummy.

Most if not all other examples from literature seem to be older than at least the 1920s.

Since death and the desire to avoid it are, and have always been, a fairly important part of human existence, the actual origin of this trope may be lost to time or not exist at all.