Thanks for your detailed response. Changing the legend position does the trick for the figure but upon printing to pdf, it still moves the whole content of the box (whether the actual box is drawn are not) to the left.
BTW, I was able to reproduce the problem with Version R2023b and Octave on another machine running Ubuntu 22 (the other computer uses Ubuntu 20). In addition, I used the online Matlab-Version provided by MathWorks so I can rule out any system-related bugs based on other packages.
Your suggestion with the fontname was helpful though, as it does not happens for monospaced fonts like Courier. So chosing one of these is a workaround for those who encounter the same problem as I did, albeit not an elegent one IMO. I also found that the blank space can be forced to appear at a different place within the legend by using braces, e.g.
leg = legend( 'Linear {}function {}with {}positive {}slope', 'Linear {}function {}with {}negative {}slope' );
produces the following pdf, which is an improvement but maybe not a viable option depending on the text in the legend. The braces take effect only in the pdf not the figure, though!
Anyway I'm sort of satisified with my plots now. It's just frustrating that the figures I want look exactly as they should and the print to pdf command messes it up unnecessarily.