Ф.Б. Миллер горячо поддержал предпринятое Шейном издание книги стихов покойного друга, поэта-самородка Василия Красова, скончавшегося в безвестности от чахотки в 1854 году. В этом сборнике, по мысли издателя, заключалось именно то, чем «умственно жило и интересовалось образованное русское общество в далеком, как и близком прошедшем…[Произведения Красова] в тридцатых и сороковых годах печатались в лучших журналах того времени наряду со стихотворениями Лермонтова, Огарева, Кольцова; многие из них с увлечением читались, перепечатывались, заучивались наизусть просвещеннейшими современниками покойного поэта, у которых они до сих пор сохранились в памяти». Важно то, что Шейн решает печатать стихи Красова в хронологическом порядке, поскольку, как он считает, это позволяет «проследить постепенное развитие поэта» (именно такой «диалектический» принцип расположения материала он примет и в своих фольклорных сборниках и назовет его «календарно-биографическим»). Однако усилия Шейна сделать стихи Красова достоянием широкого читателя пропали втуне: почти весь тираж напечатанной книги сгорел во время пожара на складе. Уцелели лишь считанные экземпляры, ставшие библиографической редкостью.
Важную вдохновляющую роль в профессиональной судьбе Шейна сыграл известный немецкий филолог, основоположник мифологической школы в фольклористике Якоб Гримм (1785-1863). Шейн свиделся с ним во время поездки за границу (в качестве домашнего учителя в одной семье), когда ему довелось посетить Берлин. Автор (вместе с братом Вильгельмом) знаменитого собрания немецких сказок, Гримм одобрил фольклорные труды Павла, с восторгом говорил о только начавших выходить «Народных русских сказках» А.Н. Афанасьева и все сокрушался, что Шейн, живя в Москве, незнаком с ним. «Непременно познакомьтесь с Афанасьевым, – настаивал Гримм. – И передайте от меня приветствие и благодарность за его сказки!»
В 1859 году в «Чтениях Общества истории и древностей российских» (кн. III), редактируемых О.М. Бодянским, был опубликован сборник былин и песен, записанных Шейном еще в 1856 году (он был издан и отдельным пятидесятистраничным оттиском под заглавием «Русские народные былины и песни, собранные П.В. Шейном»). И показательно, что именно А.Н. Афанасьев специально выделил книгу Шейна и охарактеризовал собранные им материалы как «прекрасные дополнения к сборникам Кирши Данилова и Академии наук».
Получив одобрение ученого знатока, Павел решает «отныне посвятить все свои силы и способности дальнейшему собиранию памятников народного творчества – и, по возможности, заинтересовать в пользу этого дела и других грамотных людей везде, где придется жить и служить». Он верит, что его труды послужат «маленьким подспорьем, хоть одним камушком для созидающегося фундамента народоведения у нас на Руси».
И Шейн хочет в духе времени идти в народ и просвещать его. Ненадолго он становится преподавателем одной из московских воскресных школ, в 1861 году по приглашению Л.Н. Толстого учительствует в Яснополянской школе, затем делается учителем и штатным смотрителем училищ в Туле и Епифани. И всюду он, елико возможно, собирает произведения фольклора, привлекая к сему и своих учеников, и коллег-учителей, и просто случайных знакомых. У него выработалось важное, необходимое фольклористу-профессионалу качество, о чем говорит В.Ф. Миллер: «в разговоре с простым народом Павел Васильевич умел скоро устранять всякие стеснения и заинтересовывать собеседника, напоминал сам ту или другую песню из богатого запаса своей памяти». Необходимо также отметить его участие в деятельности Русского географического общества, с коим он сотрудничал до конца жизни.