Can I use higher voltage and lower current polyfuse, which results in same power flowing through the polyfuse?
No. You should use a polyfuse with a rated IHOLD at least (and near) the maximum current that will flow thru the fuse in normal use, and a rated VMAX voltage at least the highest voltage that can be applied, including in reasonably likely fault situations, like plugging the wrong power adapter/charger (if you want assurance the polyfuse recovers from the mishap).
In most situations "the maximum current that will flow thru the fuse in normal use" does not need to account for transients like those occurring in the milliseconds of power-on, when capacitors load.
For low-voltage applications (like yours), the voltage loss on the polyfuse will typically be a significant fraction of the supply voltage, and should be accounted for. It typically subtracts from the DC power source's rated output voltage, and it's maximum value is evaluated per:
U = RMAX I
Parameters like IHOLD, VMAX, RMAX are to be taken from the polyfuse's data sheet (example).
My understanding of polyfuse is that it is a thermal device, when high current flows through it, crystalline composite heats up and breaks the circuit up to the moment it cools down enough to restore the flow of electrons. If it is a thermal device, then it should be dependent not only on current, but also on voltage, like P = U * I.
Yes, but the U is not the supply voltage. It's the voltage across the polyfuse. Polyfuses have a rated maximum voltage only so that they won't be damaged when there's a short circuit, and they get that voltage across their terminals. Fortunately, the voltage across them in normal (non-tripped) use is much lower. A more useful way to compute power dissipated in normal use is:
P = RMAX I2.
I want to protect against shortcut between positive and negative terminals, which I believe will result in full voltage flow through the polyfuse.
A short circuit will result in full voltage on the polyfuse except for some other current limitation (as there is in most switching power supplies) or significant series resistance. But that does not change the answer: you should select a polyfuse with rated IHOLD at least (and near) the maximum current in normal use (500 mA per the question). A 60 V 50 mA polyfuse does not suit the application at all: it will trip when the current exceeds some limit, at least 50 mA, probably less than 100 mA; and, for all models I know, it's series resistance will cause a prohibitively high voltage drop.
An RHEF050 (or 0808L050) would do (IHOLD = 500 mA), if the application can bear a voltage drop of up to 0.4 V (or 0.45 V) under the full 500 mA (likely more like half that when the polyfuse is new, but getting closer after the polyfuse did it's protection job and was let to cool down).