NAT: If two hosts initiate a connection to the same IP:PORT, with the same source PORT, how does the router handle it?

Solution 1:

Just because hosts A and B chose port 10123 doesn't mean that is the port that the router uses. The router connects to host C from a source port of it's own choosing. So the connection looks more like this:

                                  router
                          +--------------------+
A:(src:10123, dest:80) -> | A:10123 -> C:43775 | -> C:80
B:(src:10123, dest:80) -> | B:10123 -> C:43776 | -> C:80
                          +--------------------+

Solution 2:

I am with Laurentiu the Router will send the Packet based on the IP Address from A or B. The Response Packet would look like this:

Source IP: C
Source Port: 80
Destination IP: A (or B)
Destination Port 10123

the Router would Route the Packet to the right Host.

If the Router is configured with PAT the Router would assign the NAT/PAT IP and new random Source Ports for the outgoing Packets.