Is it possible to have xid before and after wrap around with the same timestamp? I want to create sync API in which users can get the changes since their last sync request, the API exposes cursor-based pagination (sync token)
A possible cursor may be to use updatedAt column along with xmin column (I need the xmin because many rows may have the same timestamp).
My only concern is if it's possible to have rows with same (updatedAt) timestamp and wrapped around xmin:
+---------------------+------------+
| timestamp           | xmin       |
+---------------------+------------+
| 2011-01-01 00:00:00 | 4556455456 | -&gt; first row
+---------------------+------------+
| 2011-01-01 00:00:00 | 6          | -&gt; second row, wrapped around xid
+---------------------+------------+

Within a specific timestamp (moment), I can be sure xmin will behave like a simple sequence, right?
Assuming updatedAt stores the transaction timestamp as reported by now() or CURRENT_TIMESTAMP. See:

Difference between now() and current_timestamp

Then yes, xmin behaves like a simple sequence, basically.
But you may want to look at cmin additionally. The manual:

The command identifier (starting at zero) within the inserting transaction.

Related:

How did this statement update 3 rows in Postgres?

And, subtransactions (incurring a SAVEPOINT) may very well interfere with your plans, as those advance the transaction ID (and hence the xmin of rows written after that) within the same transaction, while the transaction timestamp stays the same.
So, that's a YES to the question in the title. It is possible to have xid before and after wrap around with the same timestamp.
There are various ways subtransactions may get involved:

Calling the SQL commands manually, obviously
A PL/pgSQL block with an EXCEPTION clause
The ON_ERROR_ROLLBACK setting in Postgres
Some replication solutions involve savepoints (I think)

Related:

How to view tuples changed in a PostgreSQL transaction?

Related discussion on ppgsql-general