Stripping walls and came across these. What is the best product to use on holes that are quite deep? Also what's the best way to ensure the holes are filled correctly?
All you need is some spackle and a putty knife. Recommending brands is against policy here but any high quality spackle will do it.
Sometimes on very large holes you may have to pack it with something like crumpled newspaper (remember newspaper?) but I don't think you'll need it with the ones in your pic.
Apply the spackle with a putty knife forcing it into each hole and smooth it at the surface. On wider holes the spackle will sometimes bulge at the bottom due to gravity but don't worry about it. You can continue to work it with a damp putty knife until it sets up. After it dries, if the surface is uneven you can lightly sand down any bulges and then apply another thin coat to cover recessions or cracks.
After that you can do a final light sand or sometimes I just wipe it lightly with a damp sponge.
Then you're ready for texturing if desired.
That material really does not have the appearance of gypsum drywall. The lower holes are nearer together than would be practical to do in drywall; the upper hole seems to show a lot of sand aggregate; the wall of another hole looks to be deeper than the thickness of common drywall. All of the holes are spalled in a way that doesn't happen with drywall. It looks cementitious -- some kind of plaster on its own or applied on top of a concrete/brick/block wall.
There's no structural need to fill the holes. They could be left as they are if the new wall finish will conceal them.
If there's a cosmetic reason to fill the holes then the material and methods matter. If the wall will remain bare then you'll want something with a similar gray color. If the wall will be painted then it'll be best to use a material that soaks up paint similarly.
Drywall joint compound, spackling paste, or other patch material would be easy to work with. But if they're applied and sanded with skill they might actually look too perfectly smooth against the rest of this imperfect wall.
I'd look for something Portland cement based: [fence] post mix, thin set, tile grout, etc. The post mix really might be a good choice -- sift away the coarse gravel so that you're working with only cement powder and sand aggregates, add water to make a workable paste, and press it into the holes. Smooth the surface with a small putty knife or even just your fingertip.