TL;DR: Efficient algorithm only exist in specific cases. The problem, in its full generality (finite abelian groups) is equivalent to the integer factorization problem.
How can we effectively compute the square root of an element in a group?
One case where we can compute a square root is when the group order is known and it is odd.
Any element $g$ in a group has the following property: if $q$ is the order of the group, then $g^q=1$. This is due to Lagrage's Theorem. Equivalently, $g^{q+1}=g$. If $q$ is odd then $\frac{q+1}{2}$ is an integer, hence we can compute $h:= g^{\frac{q+1}{2}}$, which is a square root of $g$.
Another case is the following: Assume $G$ is isomorphic to the direct product group of $k$ copies of the group of order 2 and a group of order odd $q$:
$$
G \simeq \mathbb{G}_q \times \prod_{i=1}^k \mathbb{Z}_2
$$
where $\mathbb{G}_q$ denotes a group of order $q$ and $\mathbb{Z}_2$ the group of order 2. Also, importantly, assume you know how to compute this isomorphism.
In the group of order 2, the non-unit element is its own inverse, hence it has no square root. This implies the following: Let $g \in G$. Apply the isomorphism to get the representation of $g$ as an element in the direct product above: $g = (g', g_1, ..., g_k)$, where $g' \in \mathbb{G}_q$ and $g_i$ is in the $i$'th $\mathbb{Z}_2$. If there exists $i$ such that $g_i$ is not the unit element, then $g$ does not have a square root.
On the other hand, if $g_i$ is the unit element in all copies of $\mathbb{G}_2$, then the problem reduces to the case of a group of odd order: you just raise $g$ to the power of $\frac{q+1}{2}$.
Another question, if $m$ is an odd number, can we be sure there is no answer?
No. The above explains this too. Actually, for the above, you don't need to know $m$ (which is typically the case).
Is it possible to find another generator $g_1$ and an even number $k$ that satisfy the element is equal to $g^k$?
The above addresses this too, since it fully describes the set of squares in the group.
EDIT:
In "Oded Goldreich, Computational complexity: a conceptual perspective" it is shown that finding square roots modulo composite numbers is a computational problem equivalent to integer factorization. Hence, don't expect any "general purpose" algorithm, only algorithm for special cases. One such case is the multiplicative group of invertible element in a field of prime size $p$ - called Tonelli-Shanks.