OK I'm probably going to end up putting a different angle into the mix here and it won't necessarily answer your question about which language but it will give you a bit more of an idea of what areas to concentrate on.

Firstly, anything written in C# for a mobile requires the .net Compact Framework.  There are a lot of windows mobile devices out there but they are mainly used by business people and mobile enthusiasts.  They are great devices but they do have their limitations, you will also need C++ to be able to do any lower level stuff for this.

So where to next... you mentionned Java... (J2ME) it's a powerful technology and requires the right version fo the JVM on the device for on device apps to run.  Most phone providers lock their devices down and require third parties who want apps running on them to jump through hoops to do so...  The OS's that I know of that work with Java... Windows Mobile (to some degree but by no means perfectly!), Symbian (beware of version issues) and Linux... yes I did say linux on a mobile...

All the OS's will run C++ apps too... although this is a much slower and clumsier process.

The big mobile growth area at the moment is mobile web.  Now that is something you can get into without having to be constrained by a specific language, however it does mean that you need to be up on the latest mobile web best practice guidelines and ideally conform to the .mobi standards but that's not so bad as all that.

You then get to play with all sorts of technologies including mobile tv, video, payments etc.  Something that you need to be aware of in this environment however is the sometimes connectedness of mobile web... you also have to contend with the ideosyncracies of the different browsers and capabilities of devices.  What works for one may not work for all!

So where would I suggest you start... Start off with a web service that does something fun and do this in any language you like... (think about a mashup of some sort) Then create a fun UI for it that is designed to the .mobi standards and finally look into the issues of sometimes connectedness and work it from there. 

You may find that you need to learn some new skills and you will learn for yourself over time what languages work best where... one thing I will say is try not to use anything too bandwidth heavy in the UI or data transfer... as your user will get charged. 

And most importantly of course, have fun and experiment.  Figure out the areas of mobile that you are most interested in.  Saying you are fascinated by mobile is one thing.  Figuring out that it's UI, context, web services or something else is another entirely.  There are almost as many areas of mobile as there are pc software development.

I hope the above is a little helpful... also consider going along to a local mobile dev usergroup at some point, they are around here in the UK... I'm sure there will be a Mobile Monday or something similar around.