I recently found out that the latest version supports PulseAudio natively! You can download it from here. Currently, they are at version 220.127.116.11.
Previously, I had downloaded from the Medibuntu repository, which you can see here. But, they only offer version 18.104.22.168.
One thing I noticed is that they recommend version 0.9.15 or greater. You can check to see what version you have with this command:
So, here is a screenshot of the audio setup screen for this new version of Skype. Notice that PulseAudio is an option now.