I would suggest a crowbar for removing them. The overall length of the crowbar body will determine the amount of force it's capable of producing. Obviously the fulcrum will be at the end against the wall where the head turns towards the fastener.
With a relatively long crowbar, your leverage will multiply significantly and they will come out much easier.
Basically - go to any home goods store and see how long of a crowbar you feel you could live with having around - the longer the better.
As for the damage to the cement - I'm stealing a page out of another website because it's well written:
Patching such holes is a necessary part of keeping your concrete
foundation wall in good repair. If your aim is to make the wall look
better, a smooth surface is also easier to paint. An ideal patch to
use for both purposes is hydraulic cement, which expands to fill
cracks and holes as it dries.
1 Remove loose material from the hole in the wall by probing it with
the tip of a screwdriver or blade of a putty knife. Clean the hole and
surrounding area with a wire brush. Vacuum any remaining dust or
debris out of the hole.
2 Dampen the hole and surrounding area with water using a spray
3 Mix a small portion of hydraulic cement in a clean container
according to package directions. Stir the cement with a putty knife
until it has the consistency of thick peanut butter. Make only as much
cement as you can use in three minutes or less.
4 Pack hydraulic cement firmly into the hole with a putty knife or
trowel. Smooth the surface of the patch as quickly as possible before
the cement sets.
5 Spray the patch lightgly with water several times over the next 24
hours. Allow the patch to cure for 48 hours before painting, or for as
long as recommended by the manufacturer. Things You Will Need
Spray bottle filled with water
Clean mixing container
Unless the wall is well shaded, it's best to apply hydraulic cement early in the morning when the wall surface is cooler so the
cement won't dry too quickly.
Wear rubber or latex gloves when working with hydraulic cement.
Those notes apply to an interior or exterior cement surface. With a proper putty knife technique you will have a very smooth surface ideal for painting.