The readme may be wrong there. Sorry about that! Can you try removing the pip installed protobuf and using our cxx-common package (which has a lot of pre-built dependencies):
rm -rf libraries ; tar xzf libraries-llvm40-ubuntu1604-amd64.tar.gz
export TRAILOFBITS_LIBRARIES=`realpath libraries`
export PATH="${TRAILOFBITS_LIBRARIES}/cmake/bin:${TRAILOFBITS_LIBRARIES}/llvm/bin:${PATH}"
export CC="${TRAILOFBITS_LIBRARIES}/llvm/bin/clang"
export CXX="${TRAILOFBITS_LIBRARIES}/llvm/bin/clang++"
mkdir build && cd build && cmake ../remill
make -j `nproc`