Solving discrete log in partially known group
Pohlig–Hellman algorithm can't be used as is, but it can be modified to make use of known partial factorization of $n$. Suppose that you need to find such $x$ that $g^x=h$. This can be done as follows:


Choose small $k'$ such that $k'\ge k$. If the upper bound on $n$ is $n'$, then $k'=\lfloor\log_pn'\rfloor$ can be used.
Set $g'=g^{p^{k'}}$ and $h'=h^{p^{k'}}$. Now, the orders of $g'$ and $h'$ divide $s$.
Use baby-step giant-step algorithm to find discrete logarithm of $h'$ to the base $g'$. If a good upper bound on $s$ is not known, it is possible to run the algorithm multiple times with exponentially increasing upper bound.
Similarly, use baby-step giant-step algorithm to find $s$, for example, by finding discrete logarithm of $(g')^{-1}$ to the base $g'$. If $g$ is not a generator, you may find a value $s'$ different than $s$ (but it will divide $s$). In this case, $g$ lies in a subgroup of size $p^ks'$, so you may just assume that this subgroup is the whole group.
Then, use Pohlig–Hellman algorithm to find discrete logarithm of $h^s$ to the base $g^s$. Both elements are in the subgroup of size $p^k$.
Use Chinese remainder theorem to find the logarithm of $h$ to the base $g$.


To find $k$, first use the above algorithm to find $s$. Then, if you have a generator $g$, find the smallest $k$ such that $g^{p^ks}=e$, where $e$ is a neutral element. If there is no known generator, it is possible to use multiple random elements instead to make the probability of finding the correct $k$ arbitrarily close to $1$. There is no deterministic algorithm that works with arbitrary groups when no generator is known, because it is possible that all known elements will lie in the subgroup of size $p^{k-1}s$, so it will be impossible to tell that the real size is not $p^{k-1}s$ but actually $p^ks$.