Groovy, 134 Bytes

Finds all possible solutions and returns them as an array, returns [] if there isn't a solution.

{it.toList().permutations().collect{it.collate(3).every{x=Integer.parseInt(it.join(),16);(2..x**0.5).every{x%it>0};}?it.join():0}-[0]}

Example input: 123558dde
Output:

[8235d5e1d, 2dd851e35, 815e352dd, 2e3d5518d, d2d3e5581, 853de5d21, 2dd3558e1, 2dd3e5581, 2e355d18d, 2518dd3e5, dd52e3185, e1d5d5283, 823ed1d55, 28d3e515d, 28d15de35, e351258dd, e5dd21853, 851d2d3e5, ed515d283, 2dd3e5185, 85de35d21, 5d1ed5823, 8dd355e21, d2d3e5815, d2d3e5851, 251e358dd, 2dde35851, 8235d5ed1, 2dde35815, e3585dd21, d2d8153e5, 85d5d12e3, 21dd85e35, d8521de35, 21d85d3e5, e1d5d5823, e35581d2d, 3e52dd581, dd52e3851, dd52e3815, 3e5281dd5, 8dd1253e5, 3e5815d2d, 3e55d128d, ed515d823, de5853d21, e218dd355, d8d1253e5, d8d251e35, d8d5512e3, 2dde35581, 3e52dd851, 5d1ed5283, e21dd5853, 3e5d2185d, 2513e58dd, 2dd3e5815, 2dd3e5851, e1d823d55, 3e52dd815, 581d2de35, e3515d28d, 2e318dd55, ed1823d55, dd52813e5, dd52e3581, 2e3515d8d, 28d3e55d1, 82355de1d, 82355ded1, 2dde35185, 3e5d8d125, 85d21de35, 281dd53e5, d21d85e35, d21e35d85, 2dd8e1355, 28d5d1e35, 85d15d2e3, 2813e5dd5, 3e5d2d185, 5d1e5d283, 3e5d2d581, e1dd55823, 3558e12dd, d55283e1d, 15dde5283, 5d128d3e5, 5518dd2e3, e5d28315d, 5d5823ed1, d2d1853e5, 823d55e1d, de521d853, d81d552e3, 5d5823e1d, 21ded5853, 823e1dd55, 3e52dd185, 5812dde35, d85e35d21, 3e585d21d, 8512dd3e5, 3e5251d8d, d2d8513e5, e1dd55283, 2e3d81d55, 853ed5d21, 2835d1ed5, 15d2e3d85, 5d1e3528d, 15dde5823, e35851d2d, 55d283e1d, 2e3551d8d, 8dd3e5125, 85d3e5d21, 8152e3dd5, 28de1d355, e1d55d823, 8dd3e5251, 5158dd2e3, e3521dd85, e1d35528d, 2e35d185d, 21de5d853, 823d55ed1, 5813e52dd, 8153e5d2d, e1d55d283, 21de3585d, d85d21e35, 5152e3d8d, 8513e5d2d, dd5e21853, 3552dd8e1, d552e318d, e5d2835d1, 2835d1e5d, 2835d1de5, 5d1e5d823, 8dde35125, 5d52e3d81, 3e5821dd5, 28d5d13e5, e35d21d85, dd51852e3, d2d185e35, 8dde35251, 8dd2513e5, e35d2d185, 2835d5e1d, 1852e3dd5, d85d213e5, 515d8d2e3, dd53e5821, d5518d2e3, 8dd5512e3, 283d55ed1, e5d5d1823, 28d355ed1, 3e58152dd, d812e3d55, e5d85321d, d8515d2e3, d2d581e35, 3e5581d2d, 85d21d3e5, 283d55e1d, dd53e5281, 851dd52e3, e35dd5821, 3e51258dd, dd58512e3, 28d355e1d, d8d2513e5, 125e358dd, e35dd5281, e35d2d851, d8d2e3515, e35d2d815, d21853ed5, d8d2e3551, 1852dd3e5, d21853e5d, 85dd213e5, d21853de5, 5d1283e5d, 823ed155d, 5d1283de5, ed521d853, 283e1dd55, d8d355e21, d8de35251, 5d1283ed5, e35d2d581, 3e528d15d, d55283ed1, 8512dde35, 3e5851d2d, 823ed15d5, 15d28de35, 15d3e528d, 2835d5ed1, 5d12e385d, 5d185d2e3, 5d5283e1d, 55d2e3d81, d2185de35, d55e1d283, ed582315d, 2dd8513e5, 853e5d21d, e352dd581, 851e352dd, 2dd5813e5, e352dd815, 853d21e5d, e352dd851, dd5821e35, ed155d283, 3e5d8d251, d8de35125, 2e3d8d551, 3e528d5d1, e5d21d853, dd5853e21, 853d21ed5, 85de3521d, e352518dd, 2e3d8d515, 125d8de35, e352dd185, 853d21de5, 8e13552dd, 1258dde35, 581e352dd, e21d8d355, ed155d823, e21853dd5, e3528d5d1, d2d851e35, 5512e38dd, 125d8d3e5, 2e3815dd5, 2513e5d8d, 21dde5853, 355d2d8e1, d55ed1283, 815dd52e3, 283ed1d55, 8152dd3e5, 281e35dd5, 28355de1d, 355e1d28d, ed182355d, 853dd5e21, e3528d15d, ed18235d5, 15d85d2e3, e351852dd, d55e1d823, 8e12dd355, 28355ded1, 2dd815e35, 581d2d3e5, d55ed1823, 15d283ed5, 821dd53e5, 2e35d518d, 5d5283ed1, 15d283e5d, 15d283de5, e1d28355d, e5d5d1283, 251d8d3e5, e1d2835d5, dd5281e35, ed15d5823, 21de35d85, dd58152e3, 2dd1853e5, 1258dd3e5, 5d5e1d283, 1253e58dd, 3e5d8521d, 18d2e3d55, e358152dd, 5512e3d8d, e35251d8d, 853ed521d, 3e5dd5281, 5813e5d2d, ed15d5283, 18d55d2e3, 281dd5e35, 8dde21355, 1852dde35, 3e585dd21, d85e3521d, 581e35d2d, ed1283d55, d812e35d5, 2e35518dd, 5d128de35, 8153e52dd, ed55d1823, e5d82315d, e35d85d21, d812e355d, d853e521d, 8dd2e3551, 2e3581dd5, 15de5d823, 8dd2e3515, 185e35d2d, 125e35d8d, 581dd52e3, 5d5e1d823, 5812e3dd5, 5152e38dd, 3558e1d2d, 85d3e521d, 5d1d852e3, 823de55d1, 2e3d8155d, d213e585d, ed55d1283, 2e3dd5581, 2e3dd5815, 15d823ed5, 2e3dd5851, d552e3d81, 55de1d823, e5d8235d1, 21d853de5, de528315d, d21e3585d, 2e3d815d5, 21d853e5d, ed58235d1, 2e3dd5185, 21d853ed5, de52835d1, 15d823e5d, e1d28d355, 355ed128d, 5812dd3e5, 815d2d3e5, 15d823de5, 823de515d, 55de1d283, ed5853d21, 2dd8153e5, 2e3d855d1, 185dd52e3, 8e1355d2d, 2e3d55d81, d2d3558e1, d8521d3e5, e5d15d823, ed52835d1, 35528de1d, dd5e35281, 3e58dd251, 5d5ed1283, dd58213e5, e355d128d, 3e58dd125, 3e5125d8d, 8213e5dd5, 355e218dd, 2e3d8515d, 35528ded1, e5d15d283, 853e21dd5, 8dd125e35, 15ded5823, e358dd251, 2e315dd85, 851d2de35, 551d8d2e3, d2d5813e5, ed528315d, 2e3185dd5, 185d2de35, 8152dde35, e35d2185d, 15de3528d, e358dd125, 251e35d8d, 5d5ed1823, 821dd5e35, 251d8de35, 8512e3dd5, 5d1823de5, d2d815e35, 3e51852dd, 5d1823e5d, 82315dde5, 3e5dd5821, 82315de5d, 5d518d2e3, 1853e5d2d, 8dd251e35, ed128355d, e1d8235d5, 82315ded5, d21ed5853, 823ed515d, 2e38dd551, ed135528d, 2e38dd515, 5d1823ed5, 2e318d55d, 15de5d283, e1d82355d, ed1d55823, 2e3851dd5, d8d5152e3, 283de515d, 823ed55d1, 3e55812dd, dd5e35821, 15ded5283, e21355d8d, 21d85de35, 8dd5152e3, e35125d8d, e355812dd, 5d52e318d, 8e1d2d355, d8155d2e3, 3e5d21d85, 21d3e5d85, ed12835d5, de585321d, d2185d3e5, 85dd21e35, 2e318d5d5, d213e5d85, 2e385d5d1, 55d823ed1, 15d2e385d, 3e521dd85, 283de55d1, ed1d55283, d8de21355, de5d21853, 55d823e1d, d852e315d, 355d8de21, d852e35d1, 8513e52dd, 185d2d3e5, 853e5dd21, 21d3e585d, 2dd581e35, de582315d, 823e5d15d, de515d283, 185e352dd, 28de3515d, 3e5d2d815, d21de5853, 283ed155d, 3e5d2d851, 55d283ed1, 3558dde21, 283ed15d5, d815d52e3, 28de355d1, 851e35d2d, de515d823, 5d1de5823, 55dd812e3, 283e5d15d, dd55812e3, 823e5d5d1, 15dd852e3, d2de35185, 1253e5d8d, 2e35d5d81, 1853e52dd, 2e35158dd, 21dd853e5, e35185d2d, 283e5d5d1, 18dd552e3, e35281dd5, 5d13e528d, e1d283d55, 2e385d15d, 28315de5d, 85d2e35d1, 28315dde5, 2dd185e35, e3585d21d, 283ed55d1, 5d1de5283, 28315ded5, d55823ed1, 5d12e3d85, e5d853d21, e35d8d125, e358512dd, d55823e1d, 815e35d2d, e35d8d251, 18d5d52e3, 28ded1355, e3521d85d, 283ed515d, 821e35dd5, d2d3e5185, 85321de5d, d2de35815, e35d8521d, d55d812e3, e213558dd, e35815d2d, d855d12e3, 15d28d3e5, d21e5d853, 85d2e315d, 3e58512dd, d2de35851, ed128d355, 28d15d3e5, 3e52518dd, 18d2e355d, de55d1823, d2de35581, 85321ded5, d2d8e1355, d853e5d21, 18d2e35d5, 2e35d1d85, 85321dde5, 3e5185d2d, 853de521d, 355e21d8d, 5d5d812e3, 55ded1823, de55d1283, 8235d1ed5, e35821dd5, 2518dde35, 8235d1de5, 8235d1e5d, 3e521d85d, d8d125e35, 2e315d85d, ed5d21853, 55ded1283, 815d2de35, 283e1d55d, 823e1d55d, 2e355dd81, 3e5d85d21, d8d3e5125, 3e515d28d, d21d853e5, 283e1d5d5, ed585321d, 823e1d5d5, 55d2e318d, d8d3e5251, 55d18d2e3, de58235d1]

Example input: 222222222 Output: []

If anyone wants me to comment it out, holler at a brother.

Jelly, 34 30 bytes

i@€ØH’
s3µ;ZÇ€ḅ⁴µ>2aÆPẠ
Œ!ÇÐfḢ

(I should be able to use an nfind to just fetch the first match, 1# in place of ÐfḢ, for less bytes and more speed, but I'm seeing errors when I try. EDIT: wrote some changes to possibly implement this in Jelly.)

Brute force search of all permutations, filtered for the criteria, returning first match.
Way too slow for TtyItOnline. Local output examples:

C:\Jelly\jelly-master>python jelly -fu test.txt "123558DDE"
28DE1D355
C:\Jelly\jelly-master>python jelly -fu test.txt "1155578AB"
11B8A5557

How?

i@€ØH’ - Link 1, convert from hexadecimal string to integer list: string
   ØH  - yield hexadecimal characters, "0123456789ABCDEF"
i@€    - index of €ach character of s in hex chars
     ’ - decrement (vectorises) (from 1 based jelly index to place value)

s3µ;ZÇ€ḅ⁴µ>2aÆPẠ - Link 2, check if a flattened square is "all prime": string
s3               - split into threes (rows)
  µ              - monadic chain separation
   ;             - concatenate with
    Z            - transpose (columns)
     Ç€          - call last link (1) as a monad for €ach string in the list
                       -> list of integer lists
       ḅ⁴        - convert from base 16 (vectorises) -> list of decimals
         µ       - monadic chain separation
          >2     - greater than 2
            a    - and
             ÆP  - isPrime? -> list of 1s and 0s
               Ạ - all truthy?

Œ!ÇÐfḢ  - Main link: string
Œ!      - all permutations of the string
   Ðf   - filter keeping entries that evaluate to truthily for
  Ç     - last link (3) as a monad
     Ḣ  - head - return first entry

Ruby, 146 bytes

Anonymous function takes an array of nine integers, returns one solution as an array of nine integers. Relies on helper function g and a require.

require'prime'
g=->x,y,z{(2<s=x<<8|y<<4|z)&&s.prime?}
->r{r.permutation{|i|a=1
3.times{|j|a&&=g[*i[j*3,3]]&&g[i[j],i[j+3],i[j+6]]}
a&&(return i)}}

This 140-byte version prints all possible solutions, with the integers as decimals (not sure if that's allowed.)

require'prime'
g=->x,y,z{(2<s=x<<8|y<<4|z)&&s.prime?}
->r{r.permutation{|i|a=1
3.times{|j|a&&=g[*i[j*3,3]]&&g[i[j],i[j+3],i[j+6]]}
a&&p(i)}}

Ungolfed in test program

require'prime'
g=->x,y,z{(2<s=x<<8|y<<4|z)&&   #combine 3 input values, check if >2
  s.prime?}                     #and check if prime
h=->r{
  r.permutation{|i|             #iterate over all permutations
    a=1                         #a=truthy
    3.times{|j|
      a&&=g[*i[j*3,3]]&&        #check rows (3 consecutive integers)
          g[i[j],i[j+3],i[j+6]] #and columns
    }
    a&&(return i)               #if a still truthy, return solution.
  }
}

#test cases: uncomment to run. solutions do not always match example solution from OP.
a=10;b=11;c=12;d=13;e=14;f=15
#p h[[1,2,3,5,5,8,d,d,e]]   #2e3815dd5
#p h[[1,1,5,5,5,7,8,a,b]]   #a7b851551
#p h[[0,3,b,d,d,f,f,f,f]]   #ffd0dfb3f
#p h[[3,5,8,9,9,b,e,f,f]]   #8f99e3bf5
#p h[[1,5,8,9,9,b,b,d,f]]   #581bb9fd9
#p h[[1,4,6,6,7,7,9,9,f]]   #6f1469779
#p h[[1,3,3,7,8,b,c,d,d]]   #78d1cd33b
#p h[[2,4,5,7,7,b,b,d,d]]   #7274bd5db
#p h[[1,1,1,8,b,b,d,d,d]]   #11b18dbdd
#p h[[2,2,3,5,5,6,c,d,d]]   #623c25dd5
#p h[[1,2,5,5,7,8,9,9,a]]   #8a5295971
#p h[[1,1,3,5,7,9,b,b,d]]   #5b3db7191

Pyth, 23 21 bytes

f*F}R-Pd2iR16sCBc3T.p

Times out online, but finishes in 1.5 minutes on my laptop. Takes input in quotes.

Explanation

f*F}R-Pd2iR16sCBc3T.p
                   .pQ     permutations of input (implicit Q)
f                 T        filter each T:
                c3             divide into rows
              CB               make pair (rows, columns)
             s                 join those lists
         iR16                  interpret items as hex
   }R                          check if each number d is in
      Pd                           its prime factors
     -  2                          with twos removed
 *F                            product (also known as all)
                           implicitly print matches

Mathematica, 115 bytes

#<>""&@@Select[Permutations@#,And@@(PrimeQ@#&&#>2&)/@(FromDigits[#<>"",16]&/@#~Join~Transpose@#)&[#~Partition~3]&]&

The input must be a list of characters (e.g. {"1", "2", "3", "5", "5", "8", "D", "D", "E"})

J, 49 bytes

[:(#~([:*/@(2&<*1&p:)@(,&dfh|:)_3]\])"{)i.@!@#A.]

Brute-force search that tests all permutations and outputs all permutations that satisfy the conditions for the puzzle.

The performance is good enough to compute each test case in about 3 seconds.

Usage

   f =: [:(#~([:*/@(2&<*1&p:)@(,&dfh|:)_3]\])"{)i.@!@#A.]
   f '123558dde'
28de1d355
28de1d355
28de1d355
28de1d355
2e3815dd5
2e3815dd5
2e3815dd5
2e3815dd5
   timex 'f ''123558dde'''
3.68822

Explanation

[:(#~([:*/@(2&<*1&p:)@(,&dfh|:)_3]\])"{)i.@!@#A.]  Input: string S
                                             #     Length of S
                                           !@      Factorial
                                        i.@        Range [0, len(S)!)
                                                ]  Get S
                                              A.   Find the permutations of S by index
[:(                                    )           Operate on the permutations
     (                              )"{              For each permutation P
                                   ]                   Get P
                               _3]\                    Get sublists of size 3
      [:              (       )                        Operate on the sublists
                            |:                           Transpose
                        &dfh                             Convert both the transpose and
                                                         initial from hex to decimal
                       ,                                 Join them
           (        )                                  Operate on the decimals
                1&p:                                     Test each for primality
            2&<                                          Test each if greater than 2
               *                                         Multiply them (AND)
        */@                                            Reduce using multiplication
   #~                                                Filter the permutations by those
                                                     values and return

Python 2, 212 206 197 194 bytes

Requires input enclosed in quotes, like "123558dde"

from itertools import*
k,p,P=3,4,[]
while k<5e3:P+=[k][:p%k];p*=k;k+=1
print[s for s in map(''.join,permutations(input()))if all(int(s[3*i:][:3],16)in P and int(s[i::3],16)in P for i in(0,1,2))]

Saving 9 and 3 bytes thanks to Jonathan Allan

Found new prime filter from xnor (modified the square away, since we dont want 2 as prime here), old prime filter is from Bob

05AB1E, 23 21 bytes

Uses CP-1252 encoding.

œJvy3ôD€SøJìHDps2›*P—

Too slow for TIO.

Explanation

œJ                     # all permutations of input as strings
  v                    # for each permutation
                       # EXAMPLE: 2E3815DD5
   y3ô                 # split in pieces of 3
                       # EXAMPLE: ['2E3','815','DD5']
      D                # duplicate
                       # EXAMPLE: ['2E3','815','DD5'], ['2E3','815','DD5']
       €SøJ            # zip the copy to swap rows and columns 
                       # EXAMPLE: ['2E3','815','DD5'], ['28D','E1D','355']
           ì           # attach them to the same list
                       # EXAMPLE: ['2E3','815','DD5','28D','E1D','355']
            H          # convert from base 16 to base 10
                       # EXAMPLE: [739, 2069, 3541, 653, 3613, 853]
             D         # duplicate
                       # EXAMPLE: [739, 2069, 3541, 653, 3613, 853],[739, 2069, 3541, 653, 3613, 853]
              p        # check first copy for primality
                       # EXAMPLE: [739, 2069, 3541, 653, 3613, 853],[1,1,1,1,1,1]
               s2›     # check that each in second copy is larger than 2
                       # EXAMPLE: [1,1,1,1,1,1],[1,1,1,1,1,1]
                  *    # pairwise multiplication
                       # EXAMPLE: [1,1,1,1,1,1]
                   P   # product (1 if all were primes larger than 2, else 0)
                       # EXAMPLE: 1
                    —  # if 1, print y
                       # EXAMPLE: 2E3815DD5