Three replies. [edit: you started answering your own question while I was typing]
1 - A quick calculation you have certainly done yourself. A3 is 12 inches on the short side. At the consensus resolution of 300dpi, that is 3600 pixels. Your 35mm frame is ~1inch on the short side, so you need to scan at ... 3600dpi.
2 - Use your eyes, or those of a good-natured guinea pig. Small test prints; change resolutions, (double-??)blind test. I would say, with A3 prints, the subject is not allowed to stick his/her nose on the print.
3 - "Resolution" in scanner specs or tests usually means the highest lpi (2x, actually) where the stripes are still discernible. In technical terms, this means scanner resolution is defined at vanishing MTF. Which is not very meaningful. Below some MTF plots from tests of my V700 10 years ago. Not in the 4000dpi ball park, but just to illustrate the
principle.
Straight from scanner:
With the "best" parameters for MTF restoration using Gaussian USM:
In both cases, the MTF drops to zero just beyond 0.4 cycle/pixel. But the boost in MTF at 0.3 cycle/pixel, from ~0.17 to ~0.55, makes a large difference in perceived (sharpness, resolution, whatever, I'm not here for semantics).
Please note that the kind of MTF restoration I'm proposing is much less than what I sometimes see online or in shows, that just hurt the eyes. On occasion, I've brought this up to the photographer, that either admits sheepishly having sharpened maybe a
little too much, or takes a stand and claims that's how he likes his pics.