Efectivamente, el sistema integrado de validación en Laravel no admite GET como método de recepción de los datos, por lo que tendrás que validar de otra manera.
La idea es validar a mano, simplemente comprobando que tengas las entradas correctas, esto es perfectamente posible, simplemente usando PHP de toda la vida en el código de tu controlador.
Lo que no sé es si la librería captcha tiene alguna restricción para el uso de GET en vez de POST al recibir los datos, pero me figuro que no. Tendrías que usar el código PHP "nativo" para validar esta capcha, que también está explicado en el artículo del uso de no-captcha, en vez de la regla de validación que como has visto no se puede usar.
El código que creo que te resolvería esta comprobación del captcha sería este:
$captcha->verifyResponse($_GET['g-recaptcha-response'])
Eso lo puedes evaluar dentro de un condicional para saber si el captcha se resolvió correctamente. Espero que te sirva, ya nos contarás.