Add Pagination on Custom Post Type Archive

I think your query in the pagination function does not include your custom post type. Look at the Example With a Custom Query, where a category is set in the arguments. Also look how $paged is set.