Poder se puede, navegar sin permisos, pero te arriesgas a que te paren.
Personalmente nunca he solicitado ninguno, y he ido a varios embalses. Como por ejemplo al Cañón del Sil
https://es.m.wikipedia.org/wiki/Cañón_del_Sil
Incluso varias veces.
El Sil es afluente del Miño, y justo antes de unirse tiene este embalse. El Sil también tiene muchas presas, creo que es el más apresado de toda España. Todo por obtener energía.
El cañón del Sil puede recordarte a tus fiordos, con grandes placas de granito que se elevan desde el río.
Galicia, para el kayak, te ofrece mucho, y me refiero concretamente a su costa, el mar. Si quieres hacer algo tranquilo tienes las rías, una especie de fiordos, si el fiordo es un valle glaciar invadido por el mar, las rías son valles fluviales invadidos por el mar. Y si quieres algo más exigente sales a mar abierto, el Atlántico en todo su esplendor.