There is no direct way of protecting Videos against deletion using the standard Videos app.
The only way of stopping kids to delete videos is by hiding the movies. If you go to Settings->General->Restrictions->Allow Content:Movies->Select 'None'. This will hide all movies from being displayed in the Videos app, so they cannot be deleted, nor can they be played. So for watching a movie, you would temporarily change the restriction back to 'Allow all movies'.
This may not be a great solution, but it is the only one Apple gives.