('dir C:\Videos\Movies\ /ad /b /s') -> Correct.
It does not matter where you run the batch file from.
You will get errors on directories that have no MK4 files but the ones that do will rename the files. I ran the following code on my computer's music because I don't have the movies you have; and it worked...
for /f "tokens=*" %%a in ('dir C:\users\jflagg\music\ /ad /b /s') do (
ren "%%a\*.mp3" "*.mp4"
echo ren "%%a\*.mp3" "*.mp4
Why it is not working for you, I have no idea.