You can do this by using previous_post_link() and next_post_link().

These functions will create the links for you, and you should be able to get rid of all of the logic you are using for pagination.

As you wish to only link to posts in the same category you should use the functions with the following parameters:

previous_post_link('« %link', '%title', true);
next_post_link('%link »', '%title', true);

---

Update

In response to your updated question with regard to your issue of previous/next linking when they are the first/last post, please see this line from the Codex of both previous_post_link() and next_post_link() in relation to the $in_same_term parameter:

Indicates whether next post must be within the same taxonomy term as the current post. If set to ‘true’, only posts from the current taxonomy term will be displayed. If the post is in both the parent and subcategory, or more than one term, the next post link will lead to the next post in any of those terms.

With that in mind, I suspect your first last Posts may be associated with more than one category? If that’s the case the wp_get_object_terms filter may be able to help.

In your original question (pre-edit) you were only searching for posts in the very first category, so I’ll apply that logic here:

<?php add_filter('wp_get_object_terms', 'my_custom_post_navigation', 4, 99); ?>
<div id="nav-above" class="navigation">
    <div class="nav-previous">
        <?php previous_post_link( '<span class="meta-nav"> %link </span>', _x( '&#9668; Previous', 'Previous post link', 'category') , TRUE ); ?>
    </div>
    <div class="nav-previous">
        <?php next_post_link( '<span class="meta-nav"> %link </span>', _x( 'Next &#9658;', 'Next post link', 'category') , TRUE ); ?>
    </div>
</div><!-- #nav-above -->
<?php remove_filter('wp_get_object_terms', 'my_custom_post_navigation', 99); ?>

In addition to the above, you should place this in your functions.php file:

/**
 * Return only the first category when outputting the previous/next post links
 */
function my_custom_post_navigation($terms, $object_ids, $taxonomies, $args){
    
    return array_slice($terms, 0, 1);
    
}