I assume the points are meant to take integer values between $0$ and $N$.

The second question is easier. The probability that the median is $j$ is
$$\binom{j}{k} \binom{N-j}{k} / \binom{N+1}{2k+1}.$$
(I hope I'm not answering homework here. If I am, remember that you need to justify this statement to get full marks.)

The probability that $j/N$ is between $x$ and $x+dx$ is roughly $$\frac{(2k+1)!}{(k!)^2} x^k (1-x)^k dx ,$$
as $N$ goes to infinity with $k$ fixed.

When you allow repetition, you should have the same asymptopics, but the problem is just messy enough that I can't get a simple answer. My best formula is

$$\frac{(2k+1)!}{(k!)^2} \frac{1}{(N+1)^{2k+1}} \int_{x=0}^1 (x+j)^k (N-j+x)^k dx.$$

Bounding the integral by the minimum and maximum values of the integrand gives reasonable bounds. I'll provide a proof if needed.