# Python 3, <s>709</s> <s>705</s> <s>685</s> <s>664</s> <s>662</s> 615

With @ceilingcat's improvements. Accepts input from stdin.

    from string import ascii_uppercase as a
    from itertools import product as d
    import re
    n=range
    k=input()
    p=input()
    t=lambda x:x.upper().replace('J','I')
    s=[]
    for _ in t(k+a):
     if _ not in s and _ in a:s.append(_)
    m=[s[i:i+5]for i in n(0,len(s),5)]
    e={r[i]+r[j]:r[-~i%5]+r[-~j%5]for r in m for i,j in d(n(5),repeat=2)if i-j}
    e.update({c[i]+c[j]:c[-~i%5]+c[-~j%5]for c in zip(*m)for i,j in d(n(5),repeat=2)if i-j})
    e.update({m[q][r]+m[u][v]:m[q][v]+m[u][r]for q,r,u,v in d(n(5),repeat=4)if(q-u)*(r-v)})
    print(''.join(e[a+(b if b else'X')]for a,b in re.findall(r'(.)(?:(?!\1)(.))?',''.join([_ for _ in t(p)if _ in a]))))


Example:

    mfukar@oxygen[/tmp]<>$ python playfair.py
    Stack Overflow
    The cat crept into the crypt, crapped, and crept out again.
    SIRACARDFMVUICVSMORDZNAKECMZMFBCYNRDFMSVTVKBTMMY