If building a multipurposetheme (Hello Themeforest!), I would always use a Custom Post Type for something like this.
The reason is, as you already mentioned in your shortcode approach, you have too many fields and variables even in the beginning. Then, to have your Theme serve as many customers as possible, you have to add a ton of options to it, so your fields in the shortcodegenerator become uncountable.
Using the Custom post type gives you all the advantages you managed, plus one important thing to keep in mind: A custom Post Type is not an overkill. Usually. But in 99% of the cases it is just more elegant to go that way. Starting from the ability to query them, use them in various places, include them into your sitemap, a clean interface etc., there are a ton of reasons i would choose a CPT over a shortcodebased System.
Another thing to keep in mind, as you list the less messy sidemenu as a pro for the shortcodes: Build a nice Theme Option panel with the ability to deactivate your Custom Post Types. Not everyone needs a Portfolio, not everyone needs Staff.
With this ability for the User of your theme, you can speed up the performance and enhance the user experience.
And if you need a shortcode – you can also add it to display your Post Types.
Nice and structured.