Change permalink structure for pagination only

You could filter get_pagenum_link. The parameter has to be paged, not page then.

add_filter( 'get_pagenum_link', 'wpse_78546_pagenum_link' );

function wpse_78546_pagenum_link( $link )
{
    return preg_replace( '~/page/(\d+)/?~', '?paged=\1', $link );
}

But I would rather try to fix the broken rewrite rules.