How to update Time Machine's recovery partition?
The hard way: Wipe the backup drive. Set up Time Machine again to backup to this drive. Wait for the backup to complete - and find a Mavericks recovery partition on it.