You need to do a little “hack” to get pagination to work for your custom loop.
After you define $loop, do the following:
<?php
// globalize $wp_query
global $wp_query;
// copy $wp_query into a temporary variable
$temp_wp_query = $wp_query;
// nullify $wp_query
$wp_query = null;
// move $loop into $wp_query
$wp_query = $loop;
?>
At this point, your posts_nav_link() should work as expected.
Now, after the loop, swap the original object back into $wp_query, so that everything else on the page that is query-dependent will work properly:
<?php
// restore original $wp_query
$wp_query = $temp_wp_query;
?>