As I said in the comment, the issue is that cleveref's machinery is not expandable (the \@ifnextchar that hyperref complains about, for example, isn't expandable), so it can't be turned into a PDF string. The crossreftools package provides an expandable alternative for cross referencing commands...