I did have all my permissions set to "allow" for all permissions.
After going and making the change for myself from user group "super moderators" with secondary being "none" to user group "registered" and secondary being "super moderators", I now have the start a conversation option on member's profile pages.
What's strange though is my mod was set to user group "moderating" and secondary was "none" but she had the conversation option. I went ahead and changed hers to what you suggested and she still has the option for conversations.
On XenForo, all users' primary user groups should be Registered. There you'll set all the permissions you want your users to have. Then for staff user groups, all you have to do is set additional permissions you want them to have (e.g., permanently delete posts) that are revoked from your Registered user group.
Thanks for the articles, Maru. I do need to read up on them because after making the changes, I lost ability to mod the forum posts. I went ahead and made myself admin, got all my powers back including being able to start conversations. I'll leave it like that until I can read the articles and figure out why the "super mod" group is not working right for me.