Per the pull-down menu on www.AirAsia.com, AK is to begin PEN-LGK - an as-the-crow-flies distance of 70nm. (For comparison, FR's PIK-BHD is the same distance on this basis.) This consequently means AK has 12 routes from PEN (CGK and MES are operated by QZ, not AK), including 5 within Malaysia, and 3 from LGK.
According to the Mar 2010 OAG book, and confirmed on respective websites, air competition is from FY and MH. FY has 14 weekly flights in each direction (code-shared with MH) utilising AT7s with a 35-minute block time, and MH has 4 weekly services by the 734 with a 30-minute block.
There's also competition from boats; indeed, my wife and I travelled this way between the islands.