The audio output of your smartphone is fitted with a bandpass filter: high pass to protect the membrane of your earbuds/speakers against DC which would cause useless mechanical stress, and low pass to make sure as little noise is heard. Since audio is roughly 20Hz-20kHz, signals with a higher frequency will get attenuated at a rate depending on the order of the filter - at least -3dB/decade.
In fact, that output can't even accurately output digital signals up to 20kHz. Why? Because the sharp edges of the digital signals are made up by an infinite number of elementary sinusoids. The lower the cutoff frequency, the more harmonics you'll attenuate, distorting the signal like this:
You may filter what you measure to try and reconstruct the square wave but still, it's not very appealing.
Now, you can increase the datarate for a reasonable carrier frequency (say, 4kHz), by changing the modulation and/or encoding. Modulation is the process that transforms the data to send into a signal to apply to the transmission medium (through power amp. + antenna for example) - the transport layer if you will. Encoding is higher level, it deals with anomalies detection and correction. Yours is by default certainly in its simplest form (parity bits, compared to more advanced state machines etc.), but the first step to take to increase the datarate for non-critical communication is modulation.
There is a range of possible modulation techniques out there. Each one of them will have a different signal to noise ratio - error rate relationship and also a different symbol rate out for a given datarate in.
Among all of those, I recommend the simplest digital amplitude modulation. As you increase the number of possible output levels, the signal to noise ratio will decrease so you'll have to find the sweet spot. To increase your datarate by N, you'll need to be able to read 2^N different levels.
Note: Forget about the carrier (the medium is not air, so no need for RF), and in this example 0 is coded with some amplitude but it doesn't need to be.
Should you need more, you could improve your encoding to decrease the required signal to noise ratio and therefore increase the number of levels a bit further. If it's not enough, take a look at a more complex technique, e.g. QAM. ADSL used that modulation to boost the datarate on the same lines; I don't remember the symbol rate, but the carrier was around 1MHz to avoid interfering with the telephone < 4kHz, and they achieved at least 512kb/s at the time, impossible to achieve without a very dense modulation. I'm not sure if the Arduino is powerful enough for this plus your application though.