@angelazou - First let's clean up this shortcode a bit:
[bnsfc title="Notes" cat_choice="1" show_count="5" show_cats="true" only_titles="true"]
'use_thumbnails="false"' is not needed when you set 'only_titles="true"'
Now, let's break down the shortcode. The shortcode essentially takes what is displayed in your theme's standard widget area(s) and places it inline in a post.
From your specific example: "Notes" is the same as what you would see in the title of the widget block in your sidebar, again for example; you have selected category "1", which unless modified from the default installation would be those posts in the 'uncategorized' category; you are showing five (5) posts and displaying any and all categories associated with the particular post; and, last you are only showing the titles (no content/excerpt).
Now, to your question ... you are correct with setting 'show_cats="false"' (or simply leave it out of the shortcode call) will not display the "in Notes" part, but setting the title to be a link to the specific category is not currently possible with the plugin as it is written.
Can the plugin be modified, yes I imagine so; and, I will add the idea for review with future releases, but at this time I do not see that functionality being a "Five-Minute-Fix".
