I think this is what your looking for:
Custom Post Type Permalinks
This plugin lets you edit the permalink structure of custom post type.
To install this plugin:
- Download the custom-post-type-permalinks.zip file to your computer.
- Unzip the file.
- Upload the custom-post-type-permalinks directory to
your /wp-content/plugins/ directory.
- Activate the plugin through the 'Plugins' menu in WordPress.
You can also go to the 'Plugins' menu in your wordpress and click "add new". Then find this plugin by searching for "Custom Post Type Permalinks" and install it by clicking the install button.
A new item will appear in the menu on the left of your wordpress admin. Here you can change the settings depending on your needs (names of the taxonomies etc).
Futhermore my site currently has the following permalink structure "site.com/star/aristname/" which then list all posts for this artist or a page/post about this artist.
If your looking for this you can create an archive page for your custom post type. Wordpress will automaticly assume this structure. For more information on how to create your own archive page please go here. (If your indeed looking for this, I can explain it more thoroughly if you want)