Are the file types currently associated with WMP? If you double click them, do they open in WMP? Do you have another media player they might be associated with? When I right click a video file, I have them associated with MPC, so I get an option to Play with MPC.
Try this, right click a mp4 file, chose open with, then choose default program. Associate with WMP and see if the Play option doesn't now appear on right click of mp4 files. If so, repeat for other file types.