SHA256 requires lots of 32-bit rotations - about 500 per transform, plus other stuff
PIC18. They can only rotate 8-bit by one position per instruction, so you'll need about 30 to 40 instructions per rotation - 20,000 per transform. At 20MHz - 5MIPS it's about 250/sec. But PIC18 will require lots of overhead, so 100/sec would be a good rate.
PIC24. It has 16-bit rotations by arbitrary amount, so it's 4-5 instructions per rotation - 2500 per transform. At 80MHz - 40MIPS it's about 16k/sec. But other operations will weigh more, so I guess 3-5k/sec may be achived.
In both cases, it'll take a lot of creativity and hard work to achive these rates.
PIC32. It's 32-bit, so should be faster, but I'm not familiar with its instruction set.