I would repeat the selected items with their checked box on the top of the table when the user navigates to another page.
This has the benefit of keeping them visible and allow the user to uncheck one of them any time.
The drawback is when the user wants to select a lot of items, there isn't much more room for the paginated items. How to handle this depends on the available space.
Another solution is to keep a reduced representation of the selected items, like a only its name and a "x" icon to cancel each of them. This takes less space but is less readable if you don't have a title that clearly identifies the item.