During development if you get a 404 when trying to paginate with a custom post type there may be a simple explanation.
If there is a page with the same name as the custom post type the permalink rewrite rules will get confused e.g. a page called books and a custom post type with post_type key books. The solution is to name the custom post type key with the singular version, then it’s fine.