You can use the same server to also manage your DNS and nameservers, as Plesk provides this feature in the DNS Settings for each domain. It's recommended however that you use separate DNS servers so that there isn't a single point of failure (i.e., the nameservers will still be reachable if the web server temporarily goes down).
For DNS service providers, that might generate a debate if I suggest some...but it's easy enough to search for them in Google.
Parallels offers a Customer & Business Manager add-on to Plesk. This might be available from your web hosting company, but if not, Parallels sells a license for it on their site for a monthly fee: Hoster Management Pack
That would do much to automate things, as Plesk alone does not include things like automated account setup, sales, invoicing, etc...