Would your news widget be appropriate for this?
Would I need to create a testimonials category and individual blog posts for each testimonial in that category?
Sure, I’d say this would all work.
Also, I don’t personally know of any other testimonial plugins, but I’m sure if you search you can find many to try.
http://wordpress.org/extend/plugins/search.php?q=testimonials