Things will be a lot easier to calculate if you convert everything to dBm. The conversion is
P(dBm) = 10 · log10( P(mW) )
So take you maximum output power of 1000mW and you will get 30dBm. I am no expert on Germany law, but my instinct tells me that max power is after accounting for the antenna gain. The reason my instincts tell me this is that for one, it is how it is most places. And secondly, it makes logical sense. The reason for having power limits is for both limiting the interference to neighbors trying to use the same open frequency as well as for health concerns (you don't want consumer pumping dangerous amounts of RF power into places they shouldn't be). With those reasons in mind, the antenna gain affects both the interference caused to neighbors as well as the amount of energy being directed from the antenna. The technical termonolgy for this is EIRP or Equivalent isotropically radiated power. Essentially it just means, if you have a perfect omni-directional antenna, what would be effective power it would have to output to be the same as the directional antenna you are using.
So now going back to what type of antenna you can have. The access point advertises 23dBm radiated power and a 13 dBi antenna (note, the i on the dB stands for isotropic, it relates back to EIRP). What this really means is that the access point is pumping out 23-13=10dBm of power before it gets to the antenna. This means that you have 30-10=20dB of headroom for antenna gain. It is not recommended to go right up to your power ceiling as there are many things that can cause you to go over. The antenna gains and output power from your access points are just estimates (although usually pretty close), but there is no reason to risk legal issues just to get a bit more power.
The maximum distance you can transmit for is a little bit of a difficult thing to estimate and would require a lot of work on my part to explain it. In order to get any estimate at all, we have to make a lot of ideal assumptions, but real world can change things a lot. I would recommend using something like this RF Link Budget Calculator to estimate the distance you can travel. Usually the SNR is a bigger factor then the received power itself. Using a directional antenna can help improve your SNR since you wont be picking up noise from all around, but if you get too directional you may actually hurt your SNR if you don't have it aimed directly at your receiver.