creo que te estás confundiendo.
Cita: pero cuando intento registrar mi dominio en otro hosting, este me informa que el dominio ya está registrado
tu no debes de registrar el dominio en ningún hosting, pues el dominio ya está registrado (tu mismo lo dices, en dot.tk)
Lo único que debes de hacer es ir a dot.tk y cambiar los nameservers por los del nuevo hosting.