Does ServerSocket accept return socket on arbitrary port?

The Server then opens up its own next available port, and sends that to the client.

No. It creates a new socket with the same local port number. No second port number is allocated or sent to the client. The SYN/ACK segment which is the server's response to the connect request does not contain a second port number.

Here, Client A connects to the new port,

No. The client acknowledges the SYN/ACK packet and the client is connected to the original port from then on, after acknowledging the SYN/ACK. There is no second connect.

and the server now has port 5000 available again."

It always did.

I've seen answers like this in multiple questions on stackoverflow about how a different port is used in the returned socket of the accept() than the port that the ServerSocket is listening on.

Any such answer is incorrect and should be downvoted 'with extreme prejudice' and commented on adversely. The TCP handshake is defined in RFC 793 and does not specify allocation and exchange of a second port and a second connect message. There are only three messages, which isn't even enough for that to occur.

So why would the accept() need to return a socket bound to a different port?

It doesn't.

Doesn't the quartet of information sent in every header distinguish multiple connections to the same server port from different machines enough where it would not need to use different ports on the server machine for communication?

Yes.

You are correct in the TCP packet header's information. It contains:

Client IP | Client Port | Server IP | Server Port | Protocol

Or, more appropriately (since client/server become confusing when you think about bi-directional transfer):

Source IP | Source Port | Destination IP | Destination Port | Protocol

Multiple connections to the same server port will come from different ports on the client. An example may be:

0.0.0.0:45000 -> 1.1.1.1:80
0.0.0.0:45001 -> 1.1.1.1:80

The difference in client ports is enough to disambiguate the two sockets, and thus have two separate connections. There is no need for the server to open another socket on another port. It does receive a socket from the accept method, but it's assigned to the same port and is now a route back to the newly accepted client.

FTP, on the other hand, does have a model where the server will open a new unprivileged port (> 1023) and send that back to the client for the client to connect to (this is referred to as "Passive FTP"). This is to resolve issues where the client is behind a firewall and can't accept incoming data connections from the server. However, this is not the case in a typical HTTP server (or any other standard socket implementation). It's functionality that is layered on top of FTP.