an element with the same SQL SERVER key has already been added
use UNION instead of UNION ALL in this way:
SELECT DESCRIPCION AS nodeText,'DEPA' + CAST(IDDEPARTAMENTO AS VARCHAR) AS 
nodeKey,''AS nodeParentKey FROM DEPARTAMENTO
UNION ALL
SELECT DESCRIPCION AS nodeText,'PROV' + CAST(IDPROVINCIA AS VARCHAR) AS nodeKey,
'DEPA' + CAST(IDDEPARTAMENTO AS VARCHAR) AS nodeParentKey FROM PROVINCIA
UNION
SELECT DESCRIPCION AS nodeText,'DIST' + CAST(IDUBIGEO AS VARCHAR) AS nodeKey,
'PROV' + CAST(IDPROVINCIA AS VARCHAR) AS nodeParentKey FROM ubigeo

it will remove duplicates