Hmmm, have you considered using an SPI DAC chip and the onboard PIC ADC? Then you wouldn't have to deal with shift regs and thus not need the high sp clock. Thare are some micros that have built in DACs but I don't think any PICs do.
Also, if you only record the message infrequently, you could use an SPI (or I2C) eeprom and really cut down on the number of pins you need. It wouldn't work for audio delay because of the life span of the eeprom.
I don't think there are serial SRAMs out there but that would be ideal - then you could do it with a small PIC like the 16F88.
edit: forgot to mention. there is a microchip ap note on interfacing external memory -
https://www.electro-tech-online.com/custompdfs/2006/10/00869b-1.pdf