Those example scans are confusing to me since it appears that the higher resolution scan looks worse at the same scale... with a higher resolution scan you SHOULD only be seeing that pattern as you zoom in further into the image, but those appear to both be the same distance which doesn't make any sense. It's Monday so I may just be confused haha.
Ideally your final print file would be no less than 300 PPI, which would mean for A0 size you're looking at 9930 x 14040 px. If the images are all similar to what you posted (meaning soft cloud edges with no hard lines), you could enlarge the 72 PPI file to the required size and then hit it with Reduce Noise and Gaussian Blur filters until you're happy with the result... it won't be exact but it will be pretty close. If the images contain fine details, you're really kinda stuck since you're going to be working from scans that contain the print patterns from the source printer. You can try to remove the scan patterns using the Noise/Median filter, but I've had mixed results with that technique.