Let's start in the middle:
What is the furthest radius we can prove from earth, with absolute certaintity, that the laws of physics do not vary?
Zero. Proofs are found in mathematics and court rooms, and are impossible in natural science. The best we can do is have falsifiable theories. This holds for every description of reality - there's no "proof" even for the Laws of Gravity.
So, what could we observe that would tell us that physical constants or relationships between physical quantities are different in other parts of the universe, or at other times during its existence?
- Gravity: For galaxy clusters, we have independent mass measurements from several different sources that agree within their (admittedly large) error bars. Gravitational lensing, velocity dispersion of the member galaxies and X-ray temperatures are all in agreement. So the laws of gravity seem to work even at redshifts up to 0.5 or even higher.
- Atomic physics: We observe highly redshifted objects. The wavelength of the light emitted by these objects is made longer by the expansion of the universe. Observing redshifted spectral lines of different chemical elements (or molecules) tells us that atomic physics worked the same when and where this light was emitted. If the transition levels between electron orbits had changed over time, we would get different redshifts for the same objects depending on what element's spectral line we observe.
- Nucleosythesis: Shortly after the big bang, the temperature lowered such that protons and neutrons were no longer created and destroyed constantly. A free neutron has a half live of about 8.5 minutes before it decays into a proton and an electron. Our theories predict that we'd get a helium (2x proton, 2x neutron) content in the universe of about 25%. (The rest of the "normal" matter being essentially all hydrogen), and that is indeed what we observe. Now, the helium content is dependent both on the matter density at the time this took place and the half live of the neutron. From other observations (BAO come to mind) we are fairly certain that we got the matter density about right. Which leaves only a small wiggle room for the half live of the neutron, and hence for changes in the weak force.
- We've covered gravity, electromagnetism, and the weak force. I don't know any good test for the strong force.
For a change of natural laws over time, we can look at the isotope distribution in rocks here on earth. We should be able to tell whether the decay rate of various elements was different at earlier times by looking at how many of each of their decay products are around.
To summarize, we cannot say with "absolute certainty", but what we observe seems to indicate that natural laws are the same throughout the universe.