If versions that used to work fine are now slow, fairly clearly there is some local problem here.
In your reinstall, did you make sure there are no files or folders left under either the Steam Stellaris or Documents Stellaris locations, before installing again?
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 .
Please report the temperatures of your CPU and video (GPU)
1/ before starting the game up and
2/ after say 10 minutes' play.
If your PC's vendor has given you no way of reading temperatures, install
SPEEDFAN
http://www.almico.com/sfdownload.php