I think our current pagination component could be improved. Going to dump several ideas here, many of which can be mix-and-matched with what currently exists and a lot of it is up for debate.

Draft markup:

<nav aria-lablledby={uniqueId} aria-controls={tableId}>
  <h# id={uniqueId} class="visually-hidden">Pagination for table</h#>
  <button aria-label="Go to previous page, 2"> « </button>
  <ul>
    <li><button><span class="visually-hidden">Page</span> 1</button></li>
    <li><button><span class="visually-hidden">Page</span> 2</button></li>
    <li>
		<button aria-current="page" disabled>
			<span class="visually-hidden">Page</span> 3
		</button>
	</li>
    <li><button><span class="visually-hidden">Page</span> 4</button></li>
	<li><button><span class="visually-hidden">Page</span> 5</button></li>
    <li><button><span class="visually-hidden">Page</span> 6</button></li>
  </ul>
	<button aria-label="Go to next page, 4"> » </button>
</nav>

Benefits:

1. <nav> landmark makes it easier to navigate to. Though not well supported, some screen readers will let users easily navigate back to the table thanks to the addition of aria-controls. aria-labelledby will make it easy to find in rotor-like functionality.
2. <h#> makes it easier to navigate to as well. Not all screen reader users use landmarks to navigate. The addition of the heading makes it easier for those who don't. The big question here is what level heading to make it.*
3. "Previous" and "Next" buttons call out what page they will navigate to.
4. Putting the pages in a list means we don't have to maintain text like "Page 1 of 5" ourselves.
5. Using aria-current tell the screen reader what page it's currently on. Using aria-current="page" or aria-current="location" is up for debate but either is probably fine. Also marking that button as disabled sends a hit to users with a screen reader that doesn't support aria-current. Could also add more hidden text to fill that gap.

* Maybe implementing developer can configure this? Or, it can try to intelligently guess based off reading the DOM from the table maybe? Though that probably becomes much slower. Also, in a real dream world of accessible content, we could parse the the table's header (because every table will have one) and use "Pagination for {tableHeader} table" instead of the more generic heading.