I'm still on 10.8, but I would hope that this solution works for Mavericks, too:
1.) Download the "emlx to mbox Converter" from http://www.cosmicsoft.net/emlxconvert.html
2.) Open the converter (Ctrl-Click -> Open to bypass Gatekeeper).
3.) Restore the mbox from Time Machine and save it somewhere outside of the Library folder - e.g. on the desktop.
4.) Open the mbox in the Finder.
5.) Press Command-F to open the Find dialog.
6.) "Search: This Mac" will probably be selected. Change it to "Search: abc.mbox" where abc.mbox is your restored mbox.
7.) Set the search criteria to "Filename ends with .emlx". To choose "Filename", you have to choose "Other" first and then select "Filename". Do *not* use "Name" instead.
8.) The Finder will find all your e-mails.
9.) When the search has finished, select all the e-mails and drag them to the converter. For so many e-mails, this will probably already take some time. Do *not* click "Save mbox..." yet.
10.) Change the search criteria from "Filename ends with .emlx" to "Filename ends with .emlxpart".
11.) The Finder will now find the attachments.
12.) Select them all and drag them to the converter so that they're added to the list of all the mails. The converter is smart enough to figure out which attachments belong to which e-mails.
13.) Now click "Save mbox..." and save the mbox with all your e-mails somewhere, e.g. on the desktop.
14.) Finally, open Mail, choose File->Import Mailboxes, select "Files in mbox format" and import the saved file from step 13 with all your e-mails back into Mail.
15.) Move them back to the iCloud folder they should be in.
16.) Write an angry mail to Apple.
17.) Donate to the author of the converter.
(And if the e-mails are important, keep the time machine backup until you're absolutely sure all e-mails have been imported properly.)