add spans and characters into paginate_links

The function paginate_links() can return “plain”, “list” and “array” (http://codex.wordpress.org/Function_Reference/paginate_links). Just define the type as array then you’ll be to display it as you want:

<?php
    global $wp_query;

    $big = 999999999; // need an unlikely integer

    $paginate_links = paginate_links( array(
        'base'      => str_replace( $big, '%#%', get_pagenum_link( $big ) ),
        'format'    => '?paged=%#%',
        'current'   => max( 1, get_query_var('paged') ),
        'total'     => $wp_query->max_num_pages,
        'prev_text' => __('&#8592; Previous'),
        'next_text' => __('Next &#8594;'),
        'type'      => 'array'
    ));

    foreach ( $paginate_links as $pgl ) {
        echo "[ $pgl ]";
    }
?>