Odoban is made to kill the cause of odors like what you have. It seems that a liquid enzyme or oxidizer would be best.
I had to pull a dead opossum out of my grandparents walls. It crawled under the bathtub from an access hatch and died under it. After cutting out an interior section of drywall, I removed it and used a shopvac to clean the area of dirt, hair, and live maggots. Then, I spread 5 pounds of baking soda and sealed up the opening with plastic. A few days later, I vacuumed that up and sprayed it with odoban. A week later, I patched the wall. It worked well for this area.
I used to do hot water pressure washing. We cleaned the kitchens and concessions for LA Staples center, Nokia theater, Dodger stadium, many restaurants, and other commercial and residential buildings. Our units were truck mounted and were 18+ hp 3500psi and 5 gallons per minute with the heat set to 200 degrees f. The hoses were too hot to hang on to and I could turn down the pressure at the wand to clean small areas without destroying them. For tile and concrete floors, we used a surfacer similar to what you bought. The surfacer for our truck mounted carpet machine was about that size, as it had a small pump, and our other units were 24-30" wide and had suction ports to recover the water.
I like the surfacers because they get into the pores of the flooring better than scrub brushes. The small unit should work well, but it is just slow. Heat may help, but don't run hot water to your pressure washer as it is bad on the pump and seals. Our boilers were after the pump, on the high pressure side.
I don't like kilz and I think the fact that so many people recommend it is a joke. Most of them probably don't read the label and have not used it as a professional, as I have. For smoke and fire damage, I used BIN primer. It is shellac based and is thinned with alcohol. It is very nasty stuff, but is a great primer to encapsulate bad scents and it blocks out stains very well, for interior use. After using specialized treatments and washing and drying the building well, I would prime with BIN and then use an acrylic finish. The concrete may need a coating as well, but there are flooring pros here who know much more about that than I do.
OP, it seems like you don't want to try the products made specifically for pet odors, unless I missed it, and that seems like a waste when they are easy to use and not terribly expensive.
Clean the best you can, especially when the building is empty
Encapsulate the rest
Install fans if needed, but make sure they can pull in fresh air instead of creating a vacuum on the space.
Enjoy your barn/garage