Suponiendo que estamos en el directorio donde están los ficheros. Voy a renombrar todos los ficheros *.mkv de una serie que me he bajado a *.mp4. Así es como reconoce los mkv mi televisión Samsung.

En Windows se puede hacer en una sola línea desde la consola:
ren *.mkv *.mp4

Para Mac / Linux / Unix:
for f in *.mkv; do
base=`basename $f .mkv`
mv $f $base.mp4
done