Firstly note that $x_{p-n}=p-x_n$ Therefore $$\sum_{n=1}^{p-1}n\lfloor\frac{nx_n}{p}\rfloor=\sum_{n=1}^{p-1}n\frac{nx_n-1}{p}=\frac{1}{2}\sum_{n=1}^{p-1}n\frac{nx_n-1}{p}+(p-n)\frac{(p-n)(p-x_n)-1}{p}=\frac 12 \sum_{n=1}^{p-1} \frac{n^2x_n-n+(p-n)^2(p-x_n)-(p-n)}{p}=$$$$\frac 12\sum_{n=1}^{p-1}\frac{p^3-p^2x_n-2p^2n+2pnx_n+n^2p-p}{p}=\frac{1}{2}\sum_{n=1}^{p-1}p^2-px_n-2pn+2nx_n+n^2-1\equiv\frac 12\sum_{n=1}^{p-1}2+n^2-1=\frac{1}{2}\left(\frac{(p-1)p(2p-1)}{6}+2(p-1)-(p-1)\right)\equiv\frac{1}{2}(p-1)\pmod {p}$$Therefore $k=\frac{p-1}{2}$

@above I think you may have some calculating mistakes; k should be (p-1)/2