Feel free to make any change you want for your site. You can even fork the plugin if you'd like.
Are you using the latest version? The "Testimonials" title is not in the lastest version and the overall h3 title is not set by default, you have to manually add it in the shortcode for it to even show up.
As for the permalinks thing, if you add a new testimonial, or edit an existing and see the permalink and it is something other than ending in a ?p=xx where xx is some number, then the link should work just fine.
It should be in the format of http://www.yourwebsite.com/testimonials/testimonial-slug/ and that should be the exact same thing that is in the permalink spot when you edit the post in the WP dashboard. If you click view page and get a 404 error and rebuilding permalinks doesn't fix this, you probably have other issues at hand.
I'v tested it with all of the other permalink structures and only the default setting doesn't work.
I know you don't want the link and I've said we will add that feature eventually. If you need it in the meantime, feel free to change it.