We have the following relations:
$$P=a+b+c,\quad 2A=ab,\quad a^2+b^2=c^2$$
In fact, there is one more that is implicit: the triangle inequality $a+b>c$ (which follows from $a^2+b^2=c^2$). We wish to relate the first and second relations, and so after staring at the problem for a while we realize the correct course of action is to multiply $P$ by $a+b-c$ (the latter guaranteed to be positive by the triangle inequality). This gives:
$$\begin{align}P(a+b-c)&=(a+b+c)(a+b-c)=(a+b)^2-c^2\\
&=a^2+b^2+2ab-c^2=2ab=4A
\end{align}$$
Hence in general for a right triangle we have $k=A/P=(a+b-c)/4$, so the question boils down to when the difference between the sum of the lengths of the legs and the length of the hypothenuse divides or is divisible by $4$, for a right triangle with integer side-lengths.
Here we actually need to generate pythagorean triples $(a,b,c)$ such that $a,b,c$ are integers and $a^2+b^2=c^2$; the wikipedia page here gives a good picture of Euclid's formula that I recommend thinking through. Euclid's formula is the following:
$$a=m^2-n^2,\quad b=2mn\quad c=m^2+n^2$$ for integers $m>n$.
Then the quantity $a+b-c$ is $m^2-n^2+2mn-m^2-n^2=2n(m-n)$, so $A/P=k=n(m-n)/2$. The options are now that either $2$ divides $n$ or $2$ divides $m-n$, so we either have $n=2d$ and $m=k/d+2d$ or $n=d$ and $m=2(k/d)+d$ for divisors $d$ of $k$.
(to get $P/A=k$ we need $2n(m-n)$ to divide $4$, so $n(m-n)$ must divide $2$, thus $n=1$, $m=2$, $n=1$, $m=3$, and $n=2$, $m=3$ are the only solutions, giving us $(3,4,5)$, $(8,6,10)$, $(5,12,13)$ with $k=2,1,2$ being the only possibilities).
If that is all the information you have, you can't find the perimeter. If the triangle is isosceles and the leg is $x$, the area is $\frac {x^2}2$, so $x=\sqrt 2$ and the perimeter is $2\sqrt 2+2$. If the triangle has a very long leg $L$ and a short leg of length $x$, the area is $\frac 12xL$, so $L=\frac 2x$. The perimeter is then $x+L+\sqrt{x^2+L^2}\approx 2L$ which can be as large as you like.
Best Answer
Your conclusion is not exactly right. Suppose $z = 251$. Then $$k = \frac{255-251}{2} = \frac{4}{2} = 2$$ which is prime.
One solution just by looking at the Pythagorean triples might be to just figure out if any of them work with a perimeter of 510. For example, $(5, 12, 13)$ is a well-known primitive triple. Also, $$ 5a + 12a + 13a = 510 \implies a = 17 $$
Thus, $$x = 5a = 85 \\ y = 12a = 204 \\ z = 13a = 221$$ is an integer set of sides which satisfies your solution since $$k = \frac{255-221}{2} = \frac{34}{2} = 17 $$ which is prime.