Paging with category page

category.php is the main category archive template file, which is auto-magically loaded by WordPress for category archives. In that case, use the pre_get_posts hook to alter the main query for this page and you shouldn’t have trouble with the pagination.

function pregp_wpse_100602($qry) {
  if (is_category() && is_main_query()) {
    // no idea what conditions you want, but below is a sample
    // $qry->set('posts_per_page',5);
  }
}
add_action('pre_get_posts','pregp_wpse_100602');

As is, you’ve created a second loop– $loop->— for the page. The pagination functions do not work well when you do that. Those functions depend on the main query, which you are not using. I believe that is the root of the problem.

Related

WordPress pagination on custom script
https://wordpress.stackexchange.com/a/77545/21376