Haskell, 186 bytes

-- f :: [Int] -> Int -> Int f s k|let a=pure<$>0:s;d#(x:z)|let w(y:z)|d>0=[y:x:z];w _=[]=[c++y++z|c<-[]:a,y<-[]:[[x]]]++w z++map(x:)(d#z);_#_=a;d%i=iterate((++)<*>((d#)=<<))[s]!!i=[i|i<-[k..],all(`elem`0%i)$1%k]!!0 

Simple brute force solution. f takes a list of positive integers, and the DL-distance k.

This generates all strings up to the DL-distance limit k, and searches for the smallest L-distance that contains all of those strings (also by generating those strings). This saves bytes by using the same generator code for both types of distances.

Try it online! Note that this is too slow for some of the test cases, so the TIO version uses reduced test cases.

Pregolfed

Ungolfed version. Unlike the golfed version, this one removes duplicate strings during the generation, so it's also much faster:

import qualified Data.Set as S import Data.List (sortBy) import Data.Ord (comparing) snub x = S.toList $ S.fromList x f' s k = let -- 0 = any other symbol not in s alphabet = snub $ toEnum 0 : s -- all strings with L-distance 1 (if d, DL-distance) gen1 d s@(x:xs) = snub $ del ++ ins ++ sub ++ swap xs ++ map (x:) (gen1 d xs) where del = [xs] ins = map (:s) alphabet sub = map (:xs) alphabet swap (y:ys) | d = [y:x:ys] swap _ = [] gen1 _ _ = map (:[]) alphabet -- as gen1, but distance <= i genAll d i = iterate (\x->snub $ x ++ (gen1 d =<< x)) [s] !! i -- strings with DL-distance <= k sDL = S.fromAscList $ genAll True k in head [ (i, worstStrings) | -- sL = genAll False i -- zip obtains sL' = genAll False (i-1) for calculating worstStrings ((_, sL'), (i, sL)) <- zip <*> tail $ (,) <*> (S.fromAscList . genAll False) <$> [max 0(k-1)..], -- require that sL covers sDL sDL `S.isSubsetOf` sL, -- also show some maximal examples let interestingness t = length (filter (==toEnum 0) t) + abs (length t - length s) worstStrings = take 5 $ sortBy (comparing interestingness) $ S.toList (sL `S.intersection` sDL `S.difference` sL') ] 

Try it online! This uses the full testcases but Krypyp still times out on TIO (it takes a few minutes to solve). Also, it prints some of the strings that have maximal Levenshtein distance. Testcase solutions:

"hello", 3 -> 4 e.g. "eeeol","eehol","eeool","ehheo","ehhho" "world", 2 -> 4 e.g. "owrdl" "aaaaa", 1 -> 1 e.g. "_aaaa","a_aaa","aa_aa","aaa_a","aaaa" "aaaaa", 2 -> 2 e.g. "__aaa","_a_aa","_aa_a","_aaa","_aaa_" "abaaa", 3 -> 4 e.g. "aabbb","aab_b","aabb_","_aabab","_aabba" "Krypyp", 3 -> 5 e.g. "rKyKppy","rKyppKy","rKyppry","rpKyppy","r_Kyppy" "", 5 -> 5 e.g. "_____" 

Java 11, 790 764 760 bytes

import java.util.*;t->n->{var S=new HashSet<String>();int m=n;for(;m>0;)p(S,"",t+"x".repeat(m--));for(var s:(HashSet<String>)S.clone())for(m=s.length()-n;m-->1;)S.add(s.substring(m));S.removeIf(s->d(1,s,t)!=n);for(var s:S)m=Math.max(d(0,s,t),m);return m;}void p(Set S,String p,String s){int l=s.length(),i=0;if(l<1)S.add(p);for(;i<l;)p(S,p+s.charAt(i),s.substring(0,i)+s.substring(++i));}int d(int f,String s,String t){int l=s.length()+1,L=t.length()+1,d[][]=new int[l][L],i=l,j,c,q,A,B;for(;i-->0;)d[i][0]=i;for(j=0;++j<L;)for(d[i=0][j]=j;++i<l;B=t.charAt(j-1),c=A==B?0:1,d[i][j]=q=Math.min(Math.min(d[i-1][j]+1,d[i][j-1]+1),d[i-1][j-1]+c),d[i][j]=f>0&i>1&j>1&&A==t.charAt(j-2)&s.charAt(i-2)==B?Math.min(q,d[i-2][j-2]+c):q)A=s.charAt(i-1);return d[l-1][L-1];} 

Will golf it down (substantially I hope) from here.

Try it online.

Explanation:

General approach:

Input-String = t and input-integer = n in the explanation below.

1. Generate all permutations of t with up to n added characters, and add them to a Set
2. For each permutation, add a substring with up to n removed characters to the Set as well
3. Remove any String from this Set that does not have a Damerau-Levenshtein distance of n in comparison to t
4. Calculate the Levenshtein distance of each remaining String in comparison to t
5. Take the maximum, which is our result

Code explanation:

import java.util.*; // Required import for the Set and HashSet t->n->{ // Method with String and integer parameters and integer return-type var S=new HashSet<String>(); // Create a String-Set int m=n;for(;m>1;) // Loop `m` in the range [input-integer, 0): p(S,"",t // Determine all permutations of the input-String +"x".repeat(m--)); // With up to `m` additional "x" added for(var s:(HashSet<String>)S.clone()) // Loop over all generated permutations: for(m=s.length()-n;m-->1;) // Inner loop `m` in the range [permutation-length - input-integer, 1]: S.add(s.substring(m)); // Add the permutation with the first `m` characters removed to the Set as well // (NOTE: After these loops, `m` is 0 which we'll re-use later on) S.removeIf(s-> // Now remove any permutation from this Set which: d(1,s,t)!=n); // Does not have a DL-distance equal to the input-integer for(var s:S) // Loop over all remaining Strings: m=Math.max(d(0,s,t),m); // Determine the maximum L-distance return m;} // And return that maximum L-distance as result // Separated recursive method to get all permutations from a String void p(Set S,String p,String s){ // Method with Set and two String parameters and no return-type int l=s.length(), // Get the length of the input-String `s` i=0; // Index-integer `i`, starting at 0 if(l<1) // If the length is 0: S.add(p); // Add the prefix-String `p` to the Set for(;i<l;) // Loop `i` in the range [0, length): p(S,p+s.charAt(i), // Append the `i`'th character to the prefix-String `p` s.substring(0,i)+s.substring(++i));} // Remove the `i`'th character from the String `s` // And do a recursive call // Separated method to determine the DL or L distance of two Strings int d(int f,String s,String t){ // Method with integer and two String parameters and String return-type int l=s.length()+1, // Length `l` of the source-String + 1 L=t.length()+1, // Length `L` of the target-String + 1 d[][]=new int[l][L], // Create an integer matrix of those dimensions i=l,j, // Index-integers c,q,A,B; // Temp integers for(;i-->0;) // Loop `i` in the range (`l`, 0]: d[i][0]=i; // Set the `i,0`'th cell to `i` in the matrix for(j=0;++j<L;) // Loop `j` in the range [0, `L`): for(d[i=0][j]=j; // Set the `0,j`'th cell to `j` in the matrix ++i<l // Inner loop `i` in the range [0, `l`): ; // After every iteration: B=t.charAt(j-1), // Set `B` to the `j-1`'th character of the target-String c=A==B? // If the characters `A` and `B` are the same: 0 // Set `c` to 0 : // Else: 1, // Set `c` to 1 d[i][j]= // Set the `i,j`'th value to: q=Math.min( // The minimum of: Math.min( // The minimum of: d[i-1][j]+1, // The `i-1,j`'th value + 1 d[i][j-1]+1), // And the `i,j-1`'th value + 1 d[i-1][j-1]+c), // And the `i-1,j-1`'th value + `c` d[i][j]= // Then, set the `i,j`'th value to: f>0 // If the given DL-flag is 1 &i>1&j>1 // And both `i` and `j` are at least 2 &&A // And the character `A` ==t.charAt(j-2)// equals the `j-2`'th character in the target-String &s.charAt(i-2) // And the `i-2`'th character in the source-String ==B? // equals the character `B`: Math.min( // Set the `i,j`'th value to the minimum of: q, // The `i,j`'th value d[i-2][j-2]+c) // And the `i-2,j-2`'th value + `c` : // Else (the given DL-flag is 0): q) // Leave the `i,j`'th value the same A=s.charAt(i-1); // Set `A` to the `i-1`'th character of the source-String return d[l-1][L-l];} // Return the `l-1,L-1`'th value as result