Given an $m$ how to find $k$ such that $k m + 1$ is a perfect square Any way other than trying linearly for all values of $k$. 

There are infinite $k$ such that $km+1$ is a perfect square. One class of infinite solutions is given below.
For a given $m$, choose $k = a^2m + 2a$, i.e. $k = a(am+2)$ where $a \in \mathbb{Z}$. Hence, we get that $$km + 1 = (a^2m+2a)m + 1 = (am)^2 + 2(am) + 1 = (am+1)^2$$
