usually when i turn on the pc the idle temp of my cpu is 45-49 degrees celsius not comfortably hot for an idle state, but when I restart the pc the idle temp becomes lower 31-35 degrees, its weird. .
I have a xfx 8200 mobo and amd 5000+ cpu.

How long does it run before restart?

I usually restart the pc as soon as it is enable to restart after i turned it on, if I didn't restart the 45-49 idle temp will maintain until I restart it again. The 45-49 idle temp will increase as I open more heavy applications.

The only thing that comes to mind is dust/lint inside case. MIGHT also be a loose fan connection some where.

Have you got a program to check the fan speed?
If you have 2 different speeds each occasion at least you're on the way to finding a solution.

Is there a difference in the BIOS between a cold boot and a restart?

Yeah.

even though my case is mesh type I clean it regularly every week ^^, fan speeds are just fine, I'll try to reseat the heat sink. What is the proper way of applying thermal paste?

Clean residue from CPU & heat sink. apply rice grain more but not less of paste and smear w/razor bld.

Yeah. Less is more. You want a thin, even layer. Use something like a credit card to spread and use good quality paste, and make sure that you clean both surfaces before applying.

I use iso-wipes to clean the surfaces, as the alcohol evaporates.

And don't touch the CPU or Heatsink flat parts, your hands have oil on them that acts like an insulator.

Once it's down give it a very slight twist to minimise any air pockets etc, then clamp it.

I'm no expert, that's just how I do it.