In order for Start Menu search to function, the files have to be indexed. Basically... it's like a "catalogue" of files. So windows knows where they are. By default Start Menu search (and regular search if you don't specify location) won't search non-indexed locations.
I know that User files (My Documents, Downloads, Music, Pictures, Videos etc. anywhere in Libraries I believe) is indexed. So make sure the PDF's are in there, and then give it a little while to index them. (not sure exactly how long it takes to be honest)