I don't think I can help very much. I have not read the paper that you site and have not studied PBDs in any detail.
Why do you need to have blocks of size 5 for PBD-(13,{4,5}), when there is a BIBD-(13,4,lambda=1) that you can use instead?
I note that BIBDs (21,5,1) and (25,5,1) also exist. So deleting any one symbol from these would lead to designs with k={4,5}.
Adding a symbol to resolvable BIBD-(16,4,1) is another possibility.