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{1}{(N+1)^{2k+1}} $\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.
