How do I do sum of first k elements of a row of a Pascal's Triangle efficiently?
Your method is fine.  You just need to know how to do modular division.  Modular division is a bit different from division of two integers.  You can do modular division, say $x/y \bmod p$, by computing computing the modular inverse of $y$, $y^{-1}\bmod p$, and then multiplying that by $x$.  You can compute the modular inverse using the extended Euclidean algorithm.

See https://en.wikipedia.org/wiki/Modular_multiplicative_inverse. 

A slight correction:

$${n \choose j+1} = {n \choose j} \times {(n-j) \over j+1}.$$

You had an off-by-one error in the formula.  To do this modulo $p$, replace dvision by $j+1$ with multiplication by the modular inverse of $j+1$ modulo $p$.