I can report that App Store and Messages work correctly on the Z77X-UD5H without need of deleting anything or adding anything. It just works!
Having said that you need to install in the same way as it was necessary to do with Mountain Lion in order to avoid issues.
If you have a WiFi adapter do not attach or install it until after you have installed Mavericks otherwise it will take the en0 address and you will have the issues previously reported in this thread.
The process I followed is more or less exactly what is in the Official Guide except I had to specify in the bios that the USB stick I was using for install should be treated as a hard drive rather than leaving it on Auto as happens with Optimised Defaults (this may not be necessary with all USB Sticks - it was with mine or it would not boot).
Prior to running the newly created Maverick Unibeast USB Stick I removed my WiFi adaptor (TP-Link TL-WDN4800) I accepted the default setting in Multibeast for DSDT Free except changing the Disk option from 3rd Party SATA to 3rd Party eSATA as I do not use any internal devices on the the non Intel connectors and instead have one connected to an eSATA connector on the front panel of my case.
On rebooting from the Maverick hard drive after MultiBeast and reboot I immediately logged into the App Store and onto Messages with no issue whatsoever.
I have now re-installed my WiFi card and all is working as expected.
Edited to add
Just tried following that exact process that had worked earlier on using another HDD an SSD this time and even though it worked perfectly the first time - this time I am getting the errors connecting to iCloud, App Store etc...
I will continue testing and will try with the original drive again (although I doubt the issue is the type of drive).