Here's an iterative solution
(defun decode-hex-string (hex-string)
(let ((res nil))
(dotimes (i (/ (length hex-string) 2) (apply #'concat (reverse res)))
(let ((hex-byte (substring hex-string (* 2 i) (* 2 (+ i 1)))))
(push (format "%c" (string-to-number hex-byte 16)) res)))))
And one using loop, if you're looking to avoid side-effect operations (you may need to (require 'cl) in order to use this one):
(defun decode-hex-string (hex-string)
(apply #'concat
(loop for i from 0 to (- (/ (length hex-string) 2) 1)
for hex-byte = (substring hex-string (* 2 i) (* 2 (+ i 1)))
collect (format "%c" (string-to-number hex-byte 16)))))
In general, it's best to avoid recursion in Elisp and Common Lisp; your stack is going to keel over with a big enough input, and neither language guarantees tail recursion (which you aren't using, but still). In Scheme, it's a different story.
Incidentally, Happy 39th.