Here's how the first one works (or doesn't, as the case may be!).
Bear topped: Teddy decapitated gives Eddy
Car tailed: Mercedes with no tail gives merc.....
Oh, my goodness, you're right! NO k!!!! x was the unknown, certainly.
So, let's try the second one:-
He crossed the Alps, unaspirated and curly-headed
Hannibal crossed the Alps. Unaspirated (no h) he becomes annibal; curly-headed gives c at the front (primary school teachers will be familiar with "curly ku" for c, "kicking ku" for k), so we get cannibal, which was Eddy's nickname. He crossed the Alps rather more frequently than Hannibal!
Sorry for the mistake - I made it up in bed, which is where I do a lot of imagining!