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.