I think you can’t with orderby and rand. Instead you could create a custom table where you generate random integer values and connect them to the posts table. Then use posts_join filter to join your custom table to the posts query and then use posts_orderby filter to order by your joined random field. Now your random list should be paginatable.
