Rebuild all paths for a content type
Like @alias suggested, you can Create an SQL query that will go over the url_alias table and create whatever aliases you want.

Note: for a small number of nodes, the answer is much much simpler:


Go to admin/config/search/path/patterns to define the new URL pattern for that content type. 
Open the admin/content page.
Filter by a specific node type.
Check the checkbox above the content item to select all the items of the certain type. 
Select the 'update URL alias' operation.
Press 'Update'.




Two other options if you have a medium number of nodes:


Temporarily change the number of nodes per page hardcoded in core. This will allow you to use the option above with more then 20 nodes at a time.
Create a VBO content admin view to allow the user to select more then 20 nodes on a same time, then select which action to execute.