After further troubleshooting it appears the elf binary might be
malformed by patchelf run during the build process. I've tried to run
the executable on another machine and ld
complained like this:

$ ./FileStoreTest
./FileStoreTest: ./FileStoreTest: no version information available
(required by ./FileStoreTest)
./FileStoreTest: ./FileStoreTest: no version information available
(required by ./FileStoreTest)
./FileStoreTest: ./FileStoreTest: no version information available
(required by ./FileStoreTest)
./FileStoreTest: ./FileStoreTest: no version information available
(required by ./FileStoreTest)
./FileStoreTest: ./FileStoreTest: no version information available
(required by ./FileStoreTest)
./FileStoreTest: ./FileStoreTest: no version information available
(required by ./FileStoreTest)
./FileStoreTest: ./FileStoreTest: no version information available
(required by ./FileStoreTest)
./FileStoreTest: ./FileStoreTest: no version information available
(required by ./FileStoreTest)
./FileStoreTest: ./FileStoreTest: no version information available
(required by ./FileStoreTest)
./FileStoreTest: ./FileStoreTest: no version information available
(required by ./FileStoreTest)
./FileStoreTest: ./FileStoreTest: no version information available
(required by ./FileStoreTest)
./FileStoreTest: symbol lookup error: ./FileStoreTest: undefined
symbol: , version

This is the code that was supposed to simply add one extra path to the
rpath of binary files (I have added a copy-file step to make a backup
of each file too):

(add-after 'install 'fix-issue-with-libs
  (lambda* (#:key inputs outputs #:allow-other-keys)
    (chdir "..")
    (use-modules (ice-9 ftw)
(ice-9 regex)
(ice-9 rdelim)
(ice-9 popen)
(ice-9 textual-ports))
    (let* ((libdir (string-append #$output "/lib")))
      ;; ------------------------------
      ;; patchelf
      (define (get-rpaths file)
(format #t "Getting rpaths from ~a ...~%" file)
(let* ((port (open-input-pipe (string-append "patchelf --print-rpath "
file)))
       (str  (read-line port))) ; from (ice-9 rdelim)
  (close-pipe port)
  str))
      (define (patch-elf file)
      (format #t "Patching ~a ...~%" file)
(define rpath (string-append (get-rpaths file) ":" #$extra-libs "/lib"))
(display (string-append "We're setting rpath:" rpath))
(copy-file file (string-append #$output "/backup_" (car (last-pair
(string-split file #\/)))))
(invoke "patchelf" "--set-rpath" rpath file))
      (for-each (lambda (file)
  (when (elf-file? file)
    (patch-elf file)))
(find-files #$output  ".*")))))

When run in repl the patch-elf procedure shown above runs fine. It
adds the path in #$extra-libs to the rpath correctly. However when run
during the build process it most likely mangles the ELF header. At
this stage I can't be sure if it is a bug in guix (runpath check as
well as ld wrapper) or a bug in patchelf, or in the build system.

Therefore if anyone wants to have a look I attach both a binary with
the problematic elf header as well as a backup of the file above
procedure made before running patch-elf. Binaries are base64 encoded.

I used diffoscope to visualise the differences between both files, but
because of an extra offset it shows such a long output I couldn't find
an obvious difference.

Regards,
Lukasz