As a QA engineer by trade, I'd say it's good to have dedicated QA as early as you can swing it. During the initial development cycle, QA will bring a different perspective to feature planning - how fast should this run? How high does it scale? How many users can one installation support simultaneously?
A good QA engineer is constantly finding new ways to break things. Having that focus from the start is always better than bringing in QA later on in the process, demoralizing the devs who thought they were doing pretty good until the new QA folks pile hundreds of bug reports on them, which then need to be triaged (is this even a bug? If QA had been involved from the start, they'd know that this is the intended behavior! etc) and then actually fixed.
And, let's be honest here... if we're talking a startup, they're not going to be writing test plans or producing useful automation. Test plans are awesome once you have a stable product and you have some assurances that the entire UI isn't going to change, and automation is great for catching regression, but during initial development, there won't be any regressions because you haven't shipped anything yet to regress from.
Really, the important skills a good QA engineer needs are communication, stubbornness, and the ability to come up to speed fast. If QA finds a bug but can't explain clearly and concisely how it happened, what they were doing, and how to reproduce it, their usefulness rapidly dwindles.