Conservation laws seem intuitive enough with sayings like, "no free lunch", and "money doesn't grow on trees".

Incorrect, conservation laws are based on rigorous principle. Namely, Noether's theorem guarantees that for every symmetry respected by a Lagrangian, a conserved quantity results (this principle has uses outside of physics, too). So, for example, time translation invariance results in energy conservation, and space translation invariance results in the conservation of linear momentum. Invariance under rotation results in the conservation of angular momentum.

Yet the physics constants and the general framework of the laws of physics appear to work as if by magic.

This statement is only true if your knowledge of physics doesn't exceed popular science writing.

Maxwell's equations describe electromagnetic fields; we are told that E&M fields employ virtual photons to carry momentum where it needs to go. But there is something missing. Why should virtual photons obey Maxwell's equations at all?

All vector bosons satisfy the Proca equation (it's the most general equation that these fields can satisfy). In the massless limit (photons), these reduce to Maxwell's equations. Specifically, the electromagnetic wave equation.

Another example of the magical nature of physics is space-time geometry. Space-time geometry is this invisible thing that has the speed of light and other physics constants built into it.

No, the constancy of the speed of light results because of the geometry of spacetime. Every property of spacetime is a property of Lorentzian geometry, there is nothing "magical" about. I recommend reading some of rpenner's posts on these forums, he explains this fact very well.

When it curves (whatever that really means)

It means that there are non-zero Christoffel symbols, which generate geodesic deviation.

Gravitons have never been detected, so space-time geometry also works as if by magic.

Gravitons aren't necessary in general relativity. Quantum mechanics demands them, since all oscillators are quantized into modes of E = hν, and this includes gravitational waves. Spectimes geomtry leads to gravity because of the fact that particles trace out geodesics through spacetime.

There are other examples. My point is that physics exists as if by magic. Is there any hope that science might beyond to weild this kind of magic in ways that can change the laws of physics or physics constants? Will there ever be any physics "upgrades" like that allow us to do things with energy that are not allowed by normal physics?

No. Physics doesn't care about predicting how the world "really is" (although it does that quite well), it's about predicting experimental results in a coherent manner. Magic doesn't do that.

Like I mentioned, it only seems like magic if your knowledge of physics consists only of what you've read in literature directed to the general public. The purpose of such books and articles is not to derive or explain why certain things are true, just that they are. If you're actually interested in understanding physics, you need to learn and familiarize yourself with the mathematics.