How to set up redirects for category paginated pages after adding /category/ to permalink

Add the following to your .htaccess, in between the <IfModule mod_rewrite.c>:

RewriteCond %{HTTP_HOST} !^(.*)/page/$
RewriteRule ^(.*)$ /category/$1/? [R=301,L]

Your default .htaccess created from WordPress should now look like the following:

# BEGIN WordPress
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteRule ^index\.php$ - [L]
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
# Custom RewriteRule
RewriteCond %{HTTP_HOST} !^(.*)/page/$
RewriteRule ^(.*)$ /category/$1/? [R=301,L]
</IfModule>
# END WordPress