Why is the policy implied by Q-learning deterministic, when it always chooses the action with highest probability?
Q-learning uses the maximizing value at each step,

Mostly true. The target policy that Q-learning learns the action values of is the one with the maximum value. While training, Q-learning will take one action randomly (typically with a high probability of taking the action with maximum value), whilst it makes updates to value estimates assuming it will always take the maximising action next.

which implies that there is a probability distribution and it happens to choose the one with the highest probability.

Not true. This is not implied at all. The action values that Q-learning estimates are not probabilities, but expected sums of future reward. The probability distribution for exploring actions is added outside of the Q table or Q function estimate. There is no implied probability distribution of actions in the target policy. When implementing the target policy, you may decide to break ties randomly, but that is not an important detail.
It is worth noting that even if you were working with a table of action probabilities, then an agent that always chose the one with the maximum probability would be deterministic. A list of numbers from a table or non-stochastic function (which is how a Q table or Q function is implemented, and also how policy functions are implemented for methods that do process probabilities), even if it represents probabilities, cannot be random in itself. Instead, it must be interpreted by a process that decides how to use them. A process that includes a random number generator can use the numbers to generate a probability distribution that it samples from.
In Q-learning, the process that updates the Q table estimates does not include a random number generator, so as a consequence it is deterministic. However, the choice of which actions to explore is often random, and it is sometimes the case that the environment includes randomness in state transitions or reward values. So Q-learning taken as a whole is a random process.