Использование mod_rewrite для такого рода работ - не лучший вариант, поскольку вы можете заменить только фиксированное количество символов одновременно. Использование PHP, безусловно, будет проще.
Но вы можете использовать флаг "N" (Next) , чтобы возобновить замену, вызывая цикл перезаписи, пока в строке запроса есть "+":
RewriteCond %{QUERY_STRING} ^(([^&]*&)*)q=([^&+]*)\+([^&+]*\+.*)
RewriteRule ^ %{REQUEST_URI}?%1q=%3-%4 [N]
RewriteCond %{QUERY_STRING} ^(([^&]*&)*)q=([^&+]*)\+([^&+]*)&*(.*)$
RewriteRule ^ /%3-%4.html?%1%5 [L,R=301]