I took a look at the `paginate_links()` source code ([v3.5.1][1]) and there is this line ([#][2])

    $link = str_replace('%_%', 1 == $n ? '' : $format, $base);

that is giving the empty string for the n=1 page. 

With `$base = "%_%"` and `$format = "http://example.com/page/%#%/"` this becomes:

    $link = str_replace('%_%', 1 == $n ? '' : "http://example.com/page/%#%/", "%_%");

where we have 2 cases:

    n=1:     $link = str_replace('%_%', '', "%_%");

    n>1:     $link = str_replace('%_%', "http://example.com/page/%#%/", "%_%");

and after the replace:

    n=1:     $link = '';

    n>1:     $link = "http://example.com/page/%#%/";


Here is an example of the output from `paginate_links()`:

    <ul class='page-numbers'>
    	<li><a class="prev page-numbers" href="http://example.com/page/2/">&laquo; Previous</a></li>
    	<li><a class='page-numbers' href=''>1</a></li>
    	<li><a class='page-numbers' href='http://example.com/page/2/'>2</a></li>
    	<li><span class='page-numbers current'>3</span></li>
    	<li><a class='page-numbers' href='http://example.com/page/4/'>4</a></li>
    	<li><a class='page-numbers' href='http://example.com/page/5/'>5</a></li>
    	<li><a class='page-numbers' href='http://example.com/page/6/'>6</a></li>
    	<li><a class="next page-numbers" href="http://example.com/page/4/">Next &raquo;</a></li>
    </ul>

But if this would be like:
                                
    $link = str_replace('%_%', $format, $base);


then the output of `paginate_links()` would be:

    <ul class='page-numbers'>
    	<li><a class="prev page-numbers" href="http://example.com/page/2/">&laquo; Previous</a></li>
    	<li><a class='page-numbers' href='http://example.com/page/1/'>1</a></li>
    	<li><a class='page-numbers' href='http://example.com/page/2/'>2</a></li>
    	<li><span class='page-numbers current'>3</span></li>
    	<li><a class='page-numbers' href='http://example.com/page/4/'>4</a></li>
    	<li><a class='page-numbers' href='http://example.com/page/5/'>5</a></li>
    	<li><a class='page-numbers' href='http://example.com/page/6/'>6</a></li>
    	<li><a class="next page-numbers" href="http://example.com/page/4/">Next &raquo;</a></li>
    </ul>

So it looks to me that this is empty by design, at least with your setup ;-)


  [1]: http://core.trac.wordpress.org/browser/tags/3.5.1/wp-includes/general-template.php#L1922
  [2]: http://core.trac.wordpress.org/browser/tags/3.5.1/wp-includes/general-template.php#L1970