[2022] Game starts with wrong resolution

Right click on stellaris.exe , properties, compatibility. Tick "disable fullScreen optimisations" untick every other box in that dialog, Apply and exit.
Then in the launcher Game Settings menu, select fullScreen display mode, Vsync off, refresh rate 60.

Is that any better?  

DXDIAG is a program you run from the Windows search box on the task bar. After running it will open a window and start collecting info with a progress bar in the lower-left corner. When it completes click the 'save all information' button and save it to a file then attach that file here.

Please attach here your Documents/Paradox Interactive/Stellaris/settings.txt and pdx_settings.txt .
From your Documents/Paradox Interactive/Stellaris/logs/ folder, attach here system.log , error.log .  

AndrewT said: Vsync off, refresh rate 60.

I can see you haven't done this part - please try that.

If that doesn't help, I don't have anything else to suggest, I'm sorry!