Although all the posts above me are right (i.e. in physics something is proven if it works against observation), I guess a few of those formulas stem from more fundamental ideas, which cannot be proven mathematically (either because they're defined to be true or they work experimentally).
pE=mgh: The definition of work is the line integral Sum F(dot)dr. In the simple case of a constant force in one direction (i.e. gravity), moving an object against the force would result in W = F (Integral) dr = Fd=mad (F can be taken out of the integral because it is constant), and when talking about gravity we know a=g and d=h, so W=mgh.
kE=mv2/2 : Let's say we have an object moving in the +ve x direction with mass m and a speed v0 and energy E (which we don't know yet). Now let's say we apply a constant force of 1N against the object (-x direction) until it stops. Then F=ma=-1. Integrate this a few times to find the distance it takes for it to stop: mv=-t+C. We know at t=0, the initial velocity of the mass was v0, so C=mv0. We want v=0 (when the object stops), so t=C=mv0. Integrate again you get md=-1/2t2+mv0t, plug in t=mv0: md=-1/2(mv0)2+(mv0)2=1/2(mv0)2, so d=1/(2m)(mv0)2=1/2mv02. By the definition of work used before, W = F (Integral) dr = Fd=(1)(1/2)mv02. So if it took us 1/2mv02 units of energy to stop the object, it (by conservation of energy) but have had energy of 1/2mv02. This derivation makes sense, although it may not be the standard way of doing it since I just made it up...
F=Kq1q2/d^2: This comes straight from Maxwell's equations (Gauss's Law) applied to a sphere or a point. I'm not going to try to do it here just because (as I found out from the above derivation), doing math with a keyboard really sucks. What you do is just use Gauss's law on a sphere or point of charge q and find the E fiend around the object. It gets pretty easy since, because of spherical symmetry, you know the field must point radially it or out of the sphere.
F=GMm/r^2: Again, (although I haven't done this one), I'm pretty sure it's just Gauss's Law but applied to a gravity field. Note that both F=GMm/r^2 and F=Kq1q2/d^2 are examples of the "inverse square law", which, in general, described the intensity of something coming from a point particle (or sphere) with respect to distance. (Note that 1/r^2 term is *always* there).