Counter example, if I didn't botch up somewhere:

p = 23
q = 11 (so p-1=22 = 2*11)

g = 4
Actually, g has multiplicative order 11 modulo 23, as 4^11 == 1 (mod 23), but no smaller power of 4 is 1 (mod 23).

Select k=3.

Now,
4^3 mod 11 = 64 mod 11 = 9
(4^3 mod 23) mod 11 = (64 mod 23) mod 11 = 18 mod 11 = 7

QED, as they say ...