Hi Paul.
You can close this thread :-) Purging URLs with pagination, recreating them and choosing the proper duplicate SEF URL (manually) made the issue solved. sh404SEF needs to be caressed :-), it is very time consuming though ;-(
regards Tomek
Below is Weebler advise:
This sort of things usually happens when you have changed the #of item per page at some point (in the settings of K2 or Joomla menu) without purging URLs. So the number of items per page is not correct.
If so, please Purge URLs, or at least delete all the URLs with pagination in them (including duplicates).
Another reason would be if your template provide an override for the JPagination class. If so, it will overtake sh404SEF own JPagination class and pagination cannot work. You can test that by deleting paginated URLs, then switching temporarily to one of Joomla templates and see if the problem occurs the same.