If the legislators want to give people the right to be forgotten, restrictions on name changing should be the first thing to fix, way before forcing a corporation to burn books.
I don't know where you live, but actually yes, you can just change your name.
I've changed my name in Canada. Here, name changes are made public in a government newspaper. It may be the case in other countries, too.
To be more general, a name change doesn't mean anything when the change itself is recorded.
Only matters if some Nameoogle comes along and publicizes websites with name traslations joined in.
What is this thing you call "newspaper"?
I live in Germany and changing your name here is only possible for a small number of reasons. If you have a normal name aren't marrying someone or are transgender and transitioning, changing your name is effectively impossible.