I had this issue also but managed to work around it using the query module. Query module does support paginate and I have also used an INNER JOIN to get our product titles. Here is my code:
{exp:query sql="SELECT * FROM exp_store_orders INNER JOIN exp_store_order_items ON exp_store_orders.id=exp_store_order_items.order_id WHERE member_id = {exp:stash:get name='member_id'} AND exp_store_orders.order_id IS NOT NULL ORDER BY order_date DESC" parse="inward" limit="7" paginate="bottom"}
{if no_results}
<tr>
<td colspan="8">You haven't placed any orders yet!</td>
</tr>
{/if}
<tr>
<th><a href="/orders/{exp:zoo_visitor:details member_id='{member_id}'}{member:url_title}/{/exp:zoo_visitor:details}{id}" title="More Information">#{id}</a></th>
<td>{title}</td>
<td>{order_date {sn_date_default}}</td>
<td><span class="payment-status {order_status_name}">{exp:heading_title:heading_case}{order_status_name}{/exp:heading_title:heading_case}</span></td>
<td>{order_total}</td>
<td>{exp:zoo_visitor:details member_id="{member_id}"}{visitor:member_title} {visitor:member_firstname} {visitor:member_lastname}{/exp:zoo_visitor:details}</td>
<td><a href="/orders/{exp:zoo_visitor:details member_id='{member_id}'}{member:url_title}/{/exp:zoo_visitor:details}{id}" title="More Information" class="icon"><span class="icon-circle-right"></span><span class="visually-hidden">More Information</span></a></td>
</tr>
{paginate}
<tr>
<td>{pagination_links}</td>
</tr>
{/paginate}
{/exp:query}
I am using stash so that users can only see their own orders, but also the manager of the company they belong to taken from a relationship field can view the orders also. The rest are just standard variables that you would usually use from the {store_orders} tag.
I hope this helps.