Do you have any advise on what to do to get the best result?
I've tried to directly enlarge them with photoshop but the details gets lost and they look terrible.
Is there a better way to do it?
Look at stuff here
If you wanna be simple use a Mitchell filter upscale. Mitchell filtering has a minimal amount of ringing when doing an upscale. But sometimes you want ringing because that could increase the perceptual sharpness of the image...
But since your end is to print this then you also need to see how upscaling the image works along with the DPI of the image file...
But it really matters on the content what method you should use. It's subjective. Get tons of programs and try different things. Xnview, irfanview, Photoshop, illustrator... Read about the different filtering methods. See what other people do. See if converting the image to a vector with illustrator is a good idea... Do you have a decent GPU try different upscalers using cupscale. Or try this https://rasterbator.net/