> (Think displaying page 7 of 10 pages of results for example)

You don't need cookies for that. But, if you insist that you do, that can easily be a session cookie, not a stored cookie. And there's no need to obtain consent for a cookie like this, if it's not used to identify or track a (EU) person.