>How are we sure [that constants don't vary over space and time]?

Well, we test that hypothesis by looking at measurable quantities which would be different if the constant were different. This is easier to test for some constants than others.

For example, if the fine structure constant were to vary across space, that would have a major impact on chemistry — chemical bonds would have different characteristic energies, light emitted when breaking those bonds would have different wavelengths, and different kinds of bonds would be possible in general. For example, the Lyman-Alpha hydrogen line would have a wavelength different from 121.567 nm. But when we look out into the cosmos, and do spectroscopy of distant stars and galaxies, we see that they all have on average the same composition of frequencies, and the Lyman-Alpha line at 121.567 nm is strongly seen (after accounting for known effects such as redshift of course). So, that's one way we know that the fine structure constant is actually constant throughout the entire observable universe.

Likewise, for the speed of light in particular, one possible test (of many) of the speed of light in distant galaxies comes from type 1a supernovae measurements and something called the cosmic distance duality relation (CDDR), which according to the linked source is model-independent and can only be violated by three conditions (non-Riemannian geometry, which would mean general relativity itself is entirely inapplicable and which seems incredibly implausible given the successes of general relativity at modelling the cosmos as a whole, and similarities in distant measurements of other constants such as the fine-structure constant mentioned above; a source of opaqueness in the cosmos, i.e. some kind of foreground dust blocking our view of distant objects, which obviously isn't the case; and, variation in fundamental physical constants such as the speed of light). By comparing these measurements, they determine that the CDDR is respected even in distant galaxies, indicating that none of those three conditions apply.

And there are a variety of other possible tests as well; off the top of my head I vaguely recall hearing about one involving comparing the delay times of light from a certain supernova to neutrinos that were detected from the same supernova, and I think there was also one involving the delay time of light emitted directly by a supernova versus light emitted by a cloud of gas surrounding the supernova as a consequence of a shockwave, or something along those lines ... though I wasn't able to find references for these in a cursory Google search. I'm sure if you searched around you could find these and/or other methods. (Edit: Also I remembered another detail — since the speed of light is related through Maxwell's equations to the electric permittivity and magnetic permeability of the medium it's travelling in, tests of these two quantities for the vacuum or perhaps even for known kinds of systems like gas clouds surrounding a quasar or supernova in distant systems could also help confirm or refute differences in the speed of light within those systems.)

But suffice to say, the way we know it's the same is by looking at distant systems and seeing that they behave the same as nearby systems, specifically in situations where a different speed of light or other different physical constants should cause them to behave differently. To date, there is no convincing evidence of any discrepancies between the speed of light on Earth and the speed of light in distant galaxies.

Hope that makes sense!