For me, the most appropriate time to embed C code into Perl is to benefit from a probably extensive C code library by making it available to Perl programs. Especially if the C library allows access to resources close to the operating system, like i.e. for GUI programming (Wx). Taking advantage of CPU specific features like SSE might be another example. As always with optimisation, it depends on the circumstances - speed is often at the opposite end of generality.
Hashing might be faster in C for data that has very specific characteristics, but my gut feeling is that for general purpose applications, it isn't worth the effort to compete with Perls hash implementation. Same with (generally speaking) looping through arrays. Pseudo hashes might be faster already without struggeling the XPXS-interface (for Perl < 5.10 and by using fields)?
Update: typos