Automatically executing Disk Cleanup on shutdown

The group policy method should work. You say you "currently" have 3 GB of temp files - if that's the case, delete them and re-test. It's possible that is causing the time out of the script.

You also could try CCleaner (or similar). CCleaner will be more thorough than cleanmgr, being familiar with modern programs.

If you can't get group policy to work you can run it with something like Xecutor or just use CCleaner's built in "Run on start up" option for the same effect. Task Scheduler would work too.

Or if you don't want yet another process hogging your resources in the background (and you think you can remember to use it!) make a batch script along the lines of:

REM Run CCleaner silently
CCleaner.exe /AUTO
REM Shutdown after 600 seconds - tune to suit
shutdown -t 600

Not elegant, but pretty lightweight.

Try using Task Scheduler. Instructions on adding tasks on shutdown can be found here.