In Drupal Commerce, on what page does this order status fire? When an order is first paid in full
This event is triggered on whatever page request results in the named event - an order first being considered paid in full. This means it's going to vary based on the payment method. Sometimes a transaction is completed as part of a checkout form submission. Sometimes it happens while the customer is on a third party payment gateway page. Sometimes it happens after the fact when an administrator captures an authorization created during the checkout process.

When a payment transaction is saved, however it happens, Drupal Commerce compares the total of all payment transaction amounts for an order against the order total to determine whether or not the order has now been paid in full. If so, it triggers this event and updates the order to prevent the event from being triggered again - hence the "first" part of the event name.