How to construct a max heap that preserves insertion order for duplicate elements?
That's a perfectly reasonable approach.  Use (priority, insertion timestamp) as the priority value for your heap, with comparisons using lexicographic order (compare by priority, breaking ties by insertion timestamp).  That's all simple and easy to implement, and has no downsides that I can see.

Alternative, you can have one node in the priority queue per priority, with a pointer to a queue of items with that priority.  That also works and is easy to implement.