lain,
From the brief summary you have given, I would assume you would have no problem using an HCS08 device for this, especially as it appears all you have to do is record/calculate the heartrate on an incoming GPIO (probably best to route to a KBIP capable pin) and then handle the 2 UART serial ports to do file open/close/read/write via UART and also GPS ASCII data on a second UART.
As you will need 2 UART ports, that will limit your choice a little in that the lower pin count HCS08 usually have only one SCI (UART) port if any.
With that, it would appear that the QE family of processors would be a good choice as the QE16 and above all have 2 SCI ports, run at 3V and have good power saving features. The DEMOQE board is a good evaluation board for getting started and also the CPU is on a daughtercard that you can remove from the evaluation board and perhaps put on your project (NOTE: if you do this, be forewarned that the daughtercard is not fully aligned on a 0.1" matrix so you may have to fudge your connectors to your breadboard or protoboard if you are not building your own PCB). The QE16/QE32 also is available in a 28 pin SOIC, and SOIC breakout boards are readily available.
QE family web page is at: http://www.freescale.com/webapp/sps/site/prod_summary.jsp?code=S08QE&tid=m8Hp
Good luck on your project 
Alan
