It is not actually required to leave the "Powered by Zen Cart" in the footer, though it is certainly a good idea to acknowledge the source in this unobtrusive manner. You do have to leave the ZC notices in admin and in file headers. The big Templates13 notice is a real turn-off, though. It is in a sidebox which probably deliberately was not given an id so that it could not be disabled selectively in the stylesheet.
The design is simple enough that making something very similar from scratch would be easy. Make a new custom template folder per the tutorials. Starting from a copy of the template_default stylesheet, you can do most of the work by styling stock elements (the Firefox Web Developer and Firebug extensions are your best friends here). You can move the breadcrumbs code from /includes/templates/your_template/common/tpl_main_page.php to /common/tpl_header.php.
You will have to see the tradeoff between your time and the $ cost for removing their notice. I see that it says "after paying a one-time fee (per domain name / per webpage)", which could get expensive if they consider every page your site could generate separately.