Replace a character in all post titles and slugs

Slugs are saved in the very same table but in the post_name column. So your query would look like this:

UPDATE wp_posts
SET post_name = 
REPLACE(post_name, 'm' , 'p')
WHERE post_type="post" AND post_status="publish";

By the way, I’d suggest you to use $wpdb->posts instead of just wp_posts ( then it would be compatible with different prefixes, but it’s not important if it’s just a “local” script )