Make sure you're using the same resolution as that of your monitor.
Make sure your graphics drivers are completely up to date.
If you have installed mods in game, try to remove them.
Go to start (Search in Windows 8/8.1), search for power options and change power plan to High Performance.
If you have lag issues in other games too, then you should see if your graphic card is out of order.
If you're running multiple high memory taking softwares like Sony Vegas, try to turn them off before turning on game.
Turn off FPS limiter in display settings in game.
Simple. Install windows 7.
Problem solved.
Installing Windows 7 will not solve his problem, he already tried downgrading to 8/8.1
You have a good PC and it can handle any game on 4k even on maximum settings if you have a good graphic card too. Gta vice city can even run normally on a Pentium 4.