JavaScript (ES11), 63 bytes

We build the number \$q\$ as \$n\$ without the first occurrence of the digit \$n\bmod 3\$. If neither \$3\$ nor \$11\$ is a divisor of \$q\$, then \$11\$ must be a divisor of \$\lfloor q/10\rfloor\$.

Expects a BigInt and returns [k',p].

n=>eval(`q=${n}n`.replace(n%3n,""))%3n?[q%11n?q/10n:q,11]:[q,3]

Try it online!

JavaScript (ES6), 51 bytes

A more limited version without BigInts.

Expects a string and returns [k',p].

n=>(q=n.replace(n%3,""))%3?[q%11?q/10|0:q,11]:[q,3]

Try it online!

Perl 5 -pF, 61 bytes

$_/10%11||$_>111&&chop;$\=$_%11?s/@{[(sum@F)%3]}//|3:11;say}{

Try it online!

Regex (ECMAScript 2018 / Python^regex / .NET), 87 bytes

(((x+)\3{8}(?=\3$))*x|)$(?<=(?=(xx+)\4+$)(\8\6)(?<=(?=(x*)\6{9})(\1{10})*)(?<=(x*)\1*))

Try it online! - ECMAScript 2018
Attempt This Online! - Python (with regex)
Try it online! - .NET

Takes its input in unary, as a string of x characters whose length represents the number. Returns its output as the lengths of \5 (the number with a digit optionally removed) and \4 (the non-trivial factor of \5).

For golf reasons, this regex prefers to remove a digit rather than not, and always picks the leftmost digit whose removal will result in a composite number. It's actually fully general – not limited to just numbers with the digits 1 or 2 – with the caveat that it won't return a match if the input is prime and no single digit can be removed to make it composite (e.g. \$37\$).

When interpreting the explanation below, remember that these lookbehinds are evaluated from right to left – so read their contents from bottom to top, one quantified token at a time. When entering a lookahead inside a lookbehind, go back to reading from top to bottom.

                            # N = input number
(((x+)\3{8}(?=\3$))*x|)$    # \1 = a power of 10 (designates digit to be deleted)
                            #      or 0 (no digit shall be deleted);
                            # head = N; tail = 0
(?<=                        # Lookbehind
    (?=                     # Lookahead
        (xx+)\4+$           # Assert tail is composite; \4 = factor of tail
    )
    (\8\6)                  # tail = \5 = \6 + \8
                            #      = N with the digit in place \1 deleted
    (?<=                    # Lookbehind
        (?=                 # Lookahead
            (x*)\6{9}       # \6 = tail / 10
        )
        (\1{10})*           # tail = N - (N % (\1 * 10))
    )
    (?<=                    # Lookbehind
        # \8 = N % \1
        (x*)
        \1*
    )
)

Regex (PCRE2 _{^{v10.35 or later}}), 115 bytes

s/(?*(.*)(.*+))(?=(?:((?(?=\2$).?))(21|(1|2(?3)2)(?3)(12)*(?3)(2|1(?3)1)))+(?3)$)\1\K.?(.*)|(..)\9*\K.?/$8 ${9:-3}/

Attempt This Online! - PCRE2 v10.44+
Try it on regex101

This is a single regex substitution to be applied once. The appended factor will always be \$3\$, \$11\$, or \$22\$, taking advantage of this proof. It uses PCRE2's conditional syntax to append the factor, which is necessary because 3 will never be present in the input.

This uses the DFA regex ^([0369]|[258][0369]*[147]|([147]|[258][0369]*[258])([0369]|[147][0369]*[258])*([258]|[147][0369]*[147]))*$ to test for divisibility by \$3\$. Digits other than [12] are optimized out, yielding ^(21|(1|22)(12)*(2|11))*$.

s/                      # Begin substitution - match the following:
                            # No need to anchor to start, because this regex
                            # will always match when the input matches the
                            # challenge's domain of ^[12]{3,}$
    # Decide on a digit to remove; if it doesn't work out, the regex engine
    # will backtrack back into this non-atomic lookahead and try the next
    # possibility.
    (?*                     # Non-atomic lookahead
        (.*)                # \1 = the digits preceding the one to be removed
        (.*+)               # \2 = the digit to be removed and all subsequent
                            #      digits; if none need to be removed, this
                            #      will be the empty string at the end
    )
    # Prove that with that digit removed, what remains is divisible by 3.
    (?=                     # Atomic lookahead
        (?:
            ((?(?=\2$).?))  # Define and evaluate subroutine (?3): Skip a
                            # digit if it is the digit chosen to be removed.
            (
                2
                            # No need for a (?3) here, because if it's a '1'
                            # that needs removing, it can be handled by the
                            # next (?3), and if it's a '2', it can be handled
                            # by the preceding (?3).
                1
            |
                (
                    1
                |
                    2
                    (?3)
                    2
                )
                (?3)
                (
                    1
                            # No need for a (?3) here, because if it's a '2'
                            # that needs removing, it can be handled by the
                            # next (?3), and if it's a '1', it can be handled
                            # by the preceding (?3).
                    2
                )*
                (?3)
                (
                    2
                |
                    1
                    (?3)
                    1
                )
            )
        )+                  # Iterate the above loop as many times as possible,
                            # at least once
        (?3)
        $                   # Assert end of string has been reached
    )
    \1                      # Skip over the digits preceding that to be removed
    \K                      # Reset Start - exclude all previous string contents
                            # from being substituted/replaced
    .?                      # Remove the digit here, if there is one to remove
    (.*)                    # \8 = all subsequent digits
|
    # If this point is reached, it means that neither removing 1 nor 0 digits
    # would make the number divisible by 3. The only way that can happen is if
    # all digits are identical, in which case removing 1 or 0 digits is will
    # make it divisible by 11.
    (..)                    # \9 = first 2 digits
    \9*                     # Skip an even number of subsequent digits
    \K                      # Reset Start
    .?                      # Remove last digit, if number of digits was odd
/                       # Substitution - replace with the following:
    $8                      # Preserve \8 (the digits following what's removed)
    ␣                       # space
    ${9:-3}                 # if \9 is unset, "3", else \9
/                       # End substitution - no flags used

Regex (PCRE2), 126 bytes

s/(?=((?=(?|(?!.*+\2)()(1?)|(?!.*+\3)(2?)()|(1)|()(2))).)+).*\K((?!.*+\2)|(?!.*+\3)1|(?=.*+\2\3)2)(.*)|(..)\6*\K.?/$5 ${6:-3}/

Try it online! - PCRE2 v10.33
Attempt This Online - PCRE2 v10.44+
Try it on regex101

This version has the same exact output, but works by first calculating the number modulo \$3\$, the result of which will be \$0\$, \$1\$, or \$2\$, and using that to determine which digit, if any, shall be removed. As such, it does not need to guess the removed digit ahead of time, doesn't need (?*...) molecular lookahead, and is faster.

s/                 # Begin substitution - match the following:
    # Calculate the number modulo 3. Initial state is m=0.
    # m==0: \2 = unset or nonempty, \3 = anything
    # m==1: \2 = empty, \3 = unset or nonempty
    # m==2: \2 = empty, \3 = empty
    (?=                # Lookahead
        # Iterate the following loop for each digit of the input:
        (
            (?=        # Lookahead
                (?|    # Branch Reset Group - all alternatives share the same
                       # set of capture groups
                    (?!.*+\2)  # if m==0:
                    ()         #           \2 = empty
                    (1?)       # '1': m=1: \3 = nonempty
                               # '2': m=2: \3 = empty
                |
                    (?!.*+\3)  # if m==1:
                    (2?)       # '1': m=2: \2 = empty
                               # '2': m=0: \2 = nonempty
                    ()         #           \3 = empty
                |              # if m==2:
                    (1)        # '1': m=0: \2 = nonempty
                |
                    ()(2)      # '2': m=1: \2 = empty; \3 = nonempty
                )
            )
            .          # Consume digit
        )+
    )
    .*                 # Skip characters until the following match can be made
    \K                 # Reset Start - exclude all previous string contents
                       # from being substituted/replaced
    (
        (?!.*+\2)      # if m==0:
                       # remove nothing
    |
        (?!.*+\3)      # if m==1:
        1              # remove '1'
    |
        (?=.*+\2\3)    # if m==2:
        2              # remove '2'
    )
    (.*)               # \5 = all subsequent digits
|
    # If this point is reached, it means that neither removing 1 nor 0 digits
    # would make the number divisible by 3. The only way that can happen is if
    # all digits are identical, in which case removing 1 or 0 digits is will
    # make it divisible by 11.
    (..)               # \6 = first 2 digits
    \6*                # Skip an even number of subsequent digits
    \K                 # Reset Start
    .?                 # remove last digit
/                  # Substitution - replace with the following:
    $5                 # preserve \5, the digits following what is removed
    ␣                  # space
    ${6:-3}            # if \6 is unset, "3", else \6
/                  # End substitution - no flags used

05AB1E, 10 bytes

æʒp≠}θDÒθ‚

Try it online or verify all test cases.

Explanation:

æ        # Get the powerset of the (implicit) input
 ʒ       # Filter, only keeping those which are:
   ≠     #  NOT
  p      #  a prime number
 }θ      # After the filter: pop and keep the last/maximum
   D     # Duplicate it
    Ò    # Pop and get its prime factors
     θ   # Pop and keep the last/maximum again
      ‚  # Pair the two together
         # (after which this pair is output implicitly as result)

The ʒp≠} can be a number of other things with a similar result: ÐpÏK; DÒ˜K; ¤ÅPK.

Brachylog, 7 bytes

⊇PḋṀh;P

Try it online!

Outputs a list with the factor p first, and k' second.

Explanation

Since it’s been proven in a comment that it’s always possible for any input, we can state that P is a subset of the input without specifying the number of digits to remove. Since ⊇ will try the biggest subsets first (including the original input), it will succeed with at most 1 digit removed.

⊇P         P is an integer which is a subset of the input integer
  PḋṀ      P has Ṁany prime ḋivisors (at least 2, so P is composite)
    Ṁh;P   Output = [First prime divisor of P, P]

Pyth, 12 bytes

eP
e-#PTsMy`

Try it online!

Explanation

                # implicitly assign Q = eval(input())
ePe-#PTsMy`Q    # implicitly add Q
          `Q    # str(Q)
         y      # powerset
       sM       # map to integers
   -#PT         # filter for non-primes
  e             # print last value in list
eP              # print largest prime factor of value

JavaScript (Node.js), 64 bytes, string input

f=(x,p=9n)=>BigInt(a=x.replace(p%3n,''))%(b=p/3n)?f(x,-~p):[a,b]

Try it online!

JavaScript (Node.js), 68 bytes

f=(x,k=1n,p=3n)=>(a=x%k+x/k/10n*k)>p>a%p?[a,p]:f(x,p>5?k*10n:k,8n^p)

Try it online!

Fast. Use fact that input is only 1 and 2.

Proof that it's always possible: For all 1 or 2, remove one digit if odd number of digits, then it's always 11x10101; Otherwise, one of keep, remove a 1, and remove a 2 result 0 modulo 3

Neil：Edge case 111 falls under 0 modulo 3 case.

Vyxal 3, 12 bytes

ι*J⌊ᵐϩṄ¬:ḟh;

Try it Online!

Outputs largest possible k' and the first prime factor. Takes input as a string

Explained

ι*J⌊ᵐϩṄ¬:ḟh;­⁡​‎‎⁡⁠⁡‏⁠‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢‏⁠‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁤‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏‏​⁡⁠⁡‌­
ι             # ‎⁡Range 0 -> len input
 *            # ‎⁢And to each index, remove the letter at that position in the input
  J           # ‎⁣Add the input to that list so the unaltered input is an option
   ⌊          # ‎⁤Convert each to int
    ᵐϩ        # ‎⁢⁡Get the maximum by
      Ṅ¬      # ‎⁢⁢Not a prime
        :ḟ    # ‎⁢⁣Push a list of prime factors of that without popping
          h;  # ‎⁢⁤And pair the first of those with k'
💎

Created with the help of Luminespire.

Jelly,  15  13 bytes

DŒPḌẒÐḟṪÆḌṪṭƊ

A monadic Link that accepts an integer, k, and yields a pair of integers, [k', p].

Try it online!

How?

Creates the powerset of ks digits to look for candidates for k'. Jelly produces powersets that are sorted by length, so k will be at the right and all other valid k' candidates to the right of any other junk.

The code then takes, as k', the rightmost that is not prime (due to length this is also composite), which will either be k or k less one of its digits. It then tacks on the largest proper divisor of this, p.

DŒPḌẒÐḟṪÆḌṪṭƊ - Link: integer, k         e.g. 212
D             - decimal digits {k}            [2,1,2]
 ŒP           - powerset                      [[],[2],[1],[2],[2,1],[2,2],[1,2],[2,1,2]]
   Ḍ          - convert from decimal digits   [0,2,1,2,21,22,12,212]
     Ðḟ       - discard those for which:
    Ẓ         -   is prime?                   [0,1,21,22,12,212]
       Ṫ      - tail                          212
            Ɗ - last three links as a monad - f(k'=that):
        ÆḌ    -   proper divisors of k'       [1,2,4,53,106]
          Ṫ   -   tail                        106
           ṭ  -   tack to k'                  [212,106]

Charcoal, 26 bytes

Ｉ⮌⌈ＥＩＥ³Φθ⁻μ⌕θＩι⟦⌈Φι∧λ¬﹪ιλι

Try it online! Link is to verbose version of code. Explanation: Just tries removing one 1 and one 2 since by @l4m2's comment at least one of the two or three numbers will be composite. (Removing every possible digit turns out to take the same length but it will of course be slower.)

      ³                     Literal integer `3`
     Ｅ                      Map over implicit range
        θ                   Input as a string
       Φ                    Filtered where
          μ                 Current index
         ⁻                  Does not equal
           ⌕                Index of
              ι             Outer value
             Ｉ              Cast to string
            θ               In input string
    Ｉ                       Cast to integer
   Ｅ                        Map over values
                  ι         Current value
                 Φ          Filter on implicit range
                    λ       Inner value
                   ∧        Logical And
                       ι    Outer value
                     ¬﹪     Is divisible by
                        λ   Inner value
                ⌈           Take the maximum
                         ι  Current value
               ⟦            Make into list
  ⌈                         Take the maximum
 ⮌                          Reversed
Ｉ                           Cast to string
                            Implicitly print

31 bytes for a very fast version which only looks for factors below 12 (except for 11 itself, which is a special case):

Ｉ⮌⌈ＥＩＥ³Φθ⁻μ⌕θＩι⟦⌈Φ⌊⟦¹²ι⟧∧λ¬﹪ιλι

Try it online! Link is to verbose version of code.

Retina 0.8.2, 47 bytes

.|$
$`$'¶
.+
$*
1G`^(..+)\1+$
(..+)\1+$
$.& $.1

Try it online! Link includes faster test cases. Removes the earliest possible digit. Explanation:

.|$
$`$'¶

List the number with each digit removed in turn, then end with the original input.

.+
$*

Convert all of the numbers to unary.

1G`^(..+)\1+$

Keep only the first composite number.

(..+)\1+$
$.& $.1

Convert it and its highest proper factor to decimal.

In Retina 1 you would be able to fold those last two stages into a single stage, something like this:

0L$m`^(..+)\1+$
$.& $.1

(The m flag is not needed in Retina 0.8.2 because there the G stage type splits the input into lines and then matches each line in turn against the regex.)

Vyxal 3 o, 18 bytes

Ṅ[ṢḶṪ⸠LĠt“⌊ᶻṄh]ỌḄt

Try it Online!

prints k' and the largest prime factor

Ṅ[ṢḶṪ⸠LĠt“⌊ᶻṄh]ỌḄt­⁡​‎‎⁡⁠⁡‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢‏⁠‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣‏⁠‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏⁠‏​⁡⁠⁡‌⁤​‎⁠‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁤⁢‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁤⁣‏⁠‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁤⁤‏⁠⁠‏​⁡⁠⁡‌⁣⁡​‎‎⁡⁠⁢⁡⁡‏⁠‎⁡⁠⁢⁡⁢‏‏​⁡⁠⁡‌­
Ṅ                   # ‎⁡is prime?
 [                  # ‎⁢
  ṢḶṪ               # ‎⁣group sublists by length and drop the tail 
     ⸠LĠt           # ‎⁤group by max length, take the longest
         “⌊ᶻṄ       # ‎⁢⁡convert to number and filter by not prime
             h      # ‎⁢⁢take the first number left
              ]     # ‎⁢⁣
               Ọ    # ‎⁢⁤print k'
                Ḅt  # ‎⁣⁡largest prime of k'
💎

Created with the help of Luminespire.