Have your sound play when the frame matching contact with the ground is played. So if in your animation, frame 6 is where your characters foot would hit the ground, play the sound on frame 6.
For randomization, you can use a private variable and use Random(x), with x being the number of sounds you have. Then make an event for each possible variable, and play a different sound.