Chances are your Android device does not support H.264 video with a profile higher than Baseline. The profile defines what features can be used by the encoder, and the Baseline profile is one of the "lower" ones, meaning that even less powerful devices should be able to play the video.
The easiest way to re-code a video to H.264 Baseline would be to use Handbrake, and choose the Android preset from the presets drawer. Then, as H.264 Profile, choose Baseline.
For audio, select the Auto Passthru option, so you don't have to re-encode it.
You set the quality of the output by changing the Constant Quality slider. Lower values mean better quality, and higher values mean worse quality (and lower file size, of course). 22 is a good default, but you can choose anything between 18 and 28. See my CRF Guide for a bit of background info.
Once you've set that, simply re-encode your video to an MP4 file, and try playing it on the device again.