My idea was to concatenate each line, but it doesn't seem possible without resetting
Well, you're doing assignment which indeed overwrites the data. There's no attempt at concatenating anything.
If you want to grow instruction through the recurence, you'll have to pass it to each recursion. An easy way
instruction = hanoi(somed, o, i, t, );
function instruction = hanoi(d, origin, inter, target, instruction)
if d == 1
instruction = [instruction; sprintf('Move one disk from peg %s to peg %s', origin, target)];
Note that 2D char arrays require each row to be the same length, so you have to be careful that your sprintf always produces a vector the same size, regardless of the value of origin and target otherwise you'll get the error: "Dimensions of arrays being concatenated are not consistent."
Also, I presume that origin and target are supposed to be numeric, in which case %s is not the correct format specifier. See the sprintf documentation, it's %d or %u or %i for integers.