Looks like the easiest way is to select Tools > Data > Batch Editor then choose OT_Name, select Add, then put in the name.
Example:
.OT_Name=NewTrainer
Select run and it should update the name for all Pokemon in Boxes or Party, whichever tab is chosen. If you want to do both then you'll have to have Boxes selected and choose Run, then select Part and click Run again.
As always, be sure to make a backup before you make any changes.