I think that’s because the code is doing strictly what you’re telling it to do, here:
$format = empty( $permalink_structure ) ? '&page=%#%' : 'page/%#%/';
Note: '&page=%#%'.
Try building your permalink structure using add_query_arg(), which handles proper appending of & vs ?.