This does smell of an app or process getting in the way, or missing Microsoft modules, or an AV app issue. But we seem to have covered all those ...
EUIV has logs and settings, as does stellaris, but CK2 only has logs. (There are more items in the folders, like dlc signatures, but you only asked about logs and settings.)
If you delete the Documents/Paradox interactive/ folder, do all these games recreate all those files? If not, try this: Use Notepad to make a new text file called userdir.txt in the Steam Stellaris folder where stellaris.exe is (and in the equivalent folder for the other games). In that file place a single dot, save and exit. This tells the game to write the user files right there instead of under Documents. If that works and the game now runs, you can replace that dot with any file path you like.
If that doesn't help:
If you exit the Steam app entirely and just run the game .exe files, do you get any new error or message?
If you run all these installers again, what exactly happens with each one?
Please go to C:\Program Files (x86)\Steam\steamapps\common\Europa Universalis IV\_CommonRedist\DirectX\Jun2010\ and run dxsetup.exe
Please go to C:\Program Files (x86)\Steam\steamapps\common\Europa Universalis IV\_CommonRedist\vcredist\2010\ and run vcredist_x86.exe and vcredist_x64.exe
Please go to C:\Program Files (x86)\Steam\steamapps\common\Europa Universalis IV\_CommonRedist\DotNet\4.0 Client Profile\ and run dotNetFx40_Client_x86_x64.exe
Do you have any of these apps installed:
FRAPS
Plays.tv
MSI Gaming app
Evolve gaming VPN
RadeonPro
Asus AI Suite 3
AMD Gaming Evolved
Rivatuner
Roccat mouse/keyboard (hardware)
Prismatik for Lightpack
MSI Afterburner
All of them have been a problem for one or other of these games over the years, although admittedly not all of these games for any one of them.
