People often want you to tell them a story. For me this question is overreaching and I feel uncomfortable.
So I was wondering to what extend it is legal to make up a story I am fine with.
§145d StGB makes it illegal to pretend that a crime did happen or will happen, but only if one deceives the police or a similar agency. It is also a crime to deceive about the participants of a crime.
Pretending to have been sentenced and presumably to have been released after serving a sentence does not quite fit that law.
It might be Betrug, also fraud. Fraud in the German criminal law is:
"Es wird ein Anderer mit der Absicht getäuscht, dem Täter einen Vermögensvorteil zu schaffen."
On English, fraud is keeping or taking others in false belief in order of financial gain.
If there is any way for someone to get financial gain by pretending this, he might commit fraud.
Most importantly, maybe he can get some unlegal access to some rehabilitiation program or misuse some state support. Actually, murderers are generally not welcomed in Germany, but probably there are various financial resources to rehabilitate ex-criminals. He might get gain from these programs.
Typical behavior of people who had already seen prison from the inside, that they never talk about in their entire life. They are also hoping that maybe 5 years later, no one will ask, exactly what they did in these years (so they can fake something in this hole in their CV).
Murder is far above even a lesser prison sentence. I strongly disbelieve that a sane guy would just admit it. Even if he would try to cheat some social office, it would be probably more wise to fake some lesser terrible, for example some drug-related crime. "I was stupid, I was catched, I paid for what I did" <-- maybe they would even feel sorrow for that.
In their place I would lie that I was in a foreign, far country with a for them incomprehensible language, and I have worked there in a for them irrelevant industry. So they would not search or ask, because they would not see the fake advantage. They would not think so deeply to consider, maybe it was only to cover something yet much more terrible.
In any case, I believe it is not a surprise question and this guy is just insane. And he is probably insane because this country tends to put you in social isolation if they feel some weak spot in you.