If a person changed his name in 1941, then the public records should (seem) to show one person "disappearing" and another one "appearing" at the same place.
In your case, Grandfather's decision to change at a relatively young age (18) reduces the number of traces that will have been left by his former self. But the same basic principles apply.
You need to find the location of the first official reference to his new name. There is a good chance that references to the old self will be found in the same place. That is, if Fred A was working in a bakery in Manchester at age 18, then chances are that Fred B went to school in Manchester until he was 12. (Unless he was so determined to escape his old identity that she shifted across the country at the same time as changing his name.)
Genealogy often involves looking backward for traces of a person who could be an ancestor. Your task is the same with the added complication that you don't know the surname; but you do still have a given name (probably), a date of birth (even if you need to approximate) and a place.
When you find 6 Freds who might fit (or 10 or 50) then you need to look for traces of each of them after 1941. As you locate a story about a person of the same name as the child being demobbed in 1946, then you know that he was not the one who changed his name; so move on to the next. When you have only one candidate left, you have (possibly) found Grandfather.