There are a few flawed premises and irrelevancies in this question. Twain being a pseudonym is irrelevant. A rose by any other name would smell as sweet. Twain being a surname is irrelevant. Remember Cher or Oprah? Those are first names. Even Twain being a celebrity is irrelevant. Well almost.
What is important is the ability to say a name and have people know who you mean. That ability to uniquely identify them from only one name depends on context.
If I say Poe, most people think Edgar Allan Poe without any need to make sure. Unless I'm in a context where that's ambiguous. Say I have a dog named Poe. If I say, "Oh Poe is the best" in that context you can't be sure what I mean.
You are focusing on a particular context, celebrity. I know of no celebrity with the name Poe other than Edgar Allan Poe. Though I don't particularly read tabloids so I may be missing someone. What makes sense to me might not make sense to others. @RoaringFish does have a point here about this being subjective.
However, there is one very objective factor when it comes to the names of celebrities: The Screen Actors Guild. They ensure that an actors name, in the context of acting, is unique. It's one of the reasons so many actors have stage names that are different than the ones their parents gave them. It's also why there is a J in Michael J. Fox.
Ofcourse, not every celebrity is in the Guild. Not every screen actor is a celebrity. It's not a perfect system. Someone with the name Einstein might someday become a famous politician and the Guild wouldn't be able to do a thing about it. Soon people would be asking questions like, "Einstein? You mean the physicist or the politician?" It's called disambiguation. It's needed when there is more than one obvious meaning. It's why we have surnames in the first place. Famous or not.
In the end there is no perfect objective assurance of uniqueness. Any author or speaker must first make an attempt to uniquely identify the subject of discussion. Afterwords they can shorten it like I have when mentioning "the guild". I've created a context where what that means is obvious by first introducing the guild.
Sometimes there is no good way to uniquely identify someone. We have people who've done nothing wrong who can't use air travel because someone else with their name is on the no-fly list.
Celebrity itself can be thought of as the state of having been introduced to the public. It's not binary though, some remain little known their whole career. Even stars become obscure as the public's memory fades. In politics they actually measure this in polls. It's called name recognition.
So, when can a celebrity be referred to by their surname only? When doing so makes your audience think of only one person.