Inserting into your theme does not make much sense, because it's parsed prior theme display. You need to have that in your posts content prior to display (that means in $post->post_content when queried). This might not already be the case, so a reason why you currently experience that it is not paginating. The other reason why this happens is an incompatible theme.
The function that takes care about pagination in post templates (templates are a theme related part in wordpress) is called wp_link_pages(). You theme must support the multipage global variables otherwise this will never work. Those global variables are: $page, $pages, $multipage, $more, $numpages. You can learn more about their usage in setup_postdata() (undocumented function, see setup_postdata() in source).
So if you manage to get all the <!--nextpage--> fragments into your posts content and your theme supports multi pages for that custom post type template, you should be fine. The wp_link_pages() function might be handy to achieve this.