In both OP's example sentences there's no difference in meaning between fear and be afraid [of].
I have absolutely no idea why OP chose to offer the bizarre sentence I fear I have changed my gender, but I'm going to assume it's in the context of a conversation with a friend you haven't seen for a while, but was your same-sex pal. And who hasn't noticed the sex-change while you chat in a bar, and is now steering you towards the wrong sex toilets assuming you'll go in together for a pee.
Okay, that's a bit surreal. I didn't write the original sentence. It's the only interpretation I can put on it, so I'll assume it could have been I am afraid / fear I'm a bit late. Can I still buy a drink before you close the bar?.
In short, the first usage appears to be conventional politeness, meaning something like I [slightly] regret (whatever). In this usage, I fear is somewhat dated and formal-sounding.
The second usage I assume is literal, evocative of genuine anxiety, fright, or even terror. I personally perceive I fear as slightly more intense, but I doubt there's much consensus there.
TL;DR Just read the first line of the post.