If I get rid of the -Cookbook, the link works perfectly well to take you to Inline::C. The %3A%3A is just a URI-encoding of ::. Therefore I don't think there is a problem with the way the link was generated from POD. Instead I suspect that the problem is that search.cpan.org expects to be showing links to things that could be valid Perl module names. The - in your URL can't be a valid Perl module name. As confirmation, searching for Inline::C-Cookbook doesn't turn up your file.
Change the name of the file and link to Inline::C_Cookbook and everything should work just fine.