Basically, you should use this htaccess rule :
RewriteRule ^categoryname/page/([0-9]+)$ /categoryname/$1 [L,R=301]
RewriteRule ^categoryname/([0-9]+)$ /categoryname/page/$1 [L]
- The first rule change your old url
categoryname/page/3 into categoryname/3.
- The second rule is an invisible redirection from
categoryname/3 to categoryname/page/3.
Then you can use both categoryname/page/3 and categoryname/3 in your code, this will always show the short version in url.
Notice that there could have some issues with other similar url (make sure that you'll never user categoryname/3 somewhere else)
EDIT
Inifinite loop... how could I miss it !
The way to avoid this loop will be to find the "final url" for category/page/3 (for example : index.php?category_name=categoryname&page=3), and use it in your second rule :
RewriteRule ^categoryname/page/([0-9]+)$ /categoryname/$1 [L,R=301]
RewriteRule ^categoryname/([0-9]+)$ /index.php?category_name=categoryname&page=$1 [L]