If PRESENT had different permutations s would that protect it against Statistical Saturation Attack? The block cipher PRESENT is vulnerable to the Statistical Saturation Attack for up to 15 rounds (PDF) and a simple example is here.

So my questions are, if some (or all) of the permutations were changed: 


would this protect it against the Statistical Saturation Attack? 
if so, can we then use fewer than 31 rounds without causing a weakness against "other" attacks?
For your first question, there are two permutations in PRESENT that we could consider changing:


The nonlinear layer, i.e. a parallel application of an S-box.
The linear layer, which is a bitwise permutation.


The statistical saturation attack is not really based on the properties of the S-box, so one might not expect that replacing it helps a lot. However, the S-boxes do contribute to the overall diffusion of the block cipher, so the choice of the S-box does have an impact. The paper that you mentioned contains a detailed discussion of the influence of the S-box in Section 4 (starting on page 12). They conclude that


  It is noticeable that the PRESENT S-box is among the worst possible
  choices to resist our attack.


This is very clear from Figure 14 in Appendix D.

A better countermeasure would be to replace the bitwise permutation, as it is the cause of the vulnerability. The linear layer of PRESENT leads to other attacks as well, in particular linear cryptanalysis. For instance, Cho's Linear Cryptanalysis of Reduced-Round PRESENT is based on the limited diffusion provided by this bitwise permutation in combination with the existence of one-bit trails for the S-boxes.

The paper proposing the recent cipher GIFT contains some ideas on how to choose a good permutation in a PRESENT-like block cipher. They don't revisit the statistical saturation attack though.

For your second question (can we use less than 31 rounds), it depends a lot on what the new S-box and linear layer are. The statistical saturation attack can be stretched up to 24 rounds, see these errata and improvements for the correct complexities. Multivariate linear cryptanalysis can reach at most 26 or (maybe) 27 rounds. Replacing the bitwise permutation with a much stronger linear layer could prevent both of these attacks, but it's not possible to rule out other attacks (especially if we don't know what the replacement is).