There wasn't really a big renaming process started which could have failed.
The closest it ever came to a renaming was in 1994, when an independent commission for the renaming of streets suggested to rename half of the Karl-Marx-Allee to Hegelallee (the other half was suggested to remain named after Marx). The local mayor objected because of the costs and a bad budget, and the senator of the right-wing CDU rejected the proposal.
Other than that, far-right fringe groups have from time to time proposed to rename the street, but were never successful and there were no other processes started which could have failed.
The reason is likely that renaming streets is difficult (you need to agree on a new name, and the legal process is often complex) and expensive (especially for businesses located in the street). That is for example the reason why the process of renaming street names such as those in the Afrikanisches Viertel takes so long.
And why would one start such a difficult and expensive process to rename the Karl-Marx-Allee? Marx was an important German philosopher and is not really related to Stalin.
If being a reference point for later ideologies or being deemed offensive when looking at it from today's morals is reason for renaming, then there would a be lot of streets to rename, e.g. Martin-Luther-Straße, Richard-Wagner-Straße, or Treitschkestraße. Things are even still named after people directly associated with national socialism, such as Rommel, Hanns Martin Schleyer, etc. That not even these were renamed shows how difficult the process of renaming is.