Is the "king" in "King Arthur" a proper adjective?

No, because king is not an adjective at all, but rather a noun. However, together with Arthur, it forms a proper name with a composite head. The noun king is capitalized (King Arthur) because of the following rule:

Civil, military, religious, and professional titles are capitalized when they immediately precede a personal name and are thus used as part of the name.
                                                                                               the Chicago Manual of Style

Discussion

Status of King as a noun

The first question is why am I so sure king is not an adjective in King Arthur. Before I answer that, it will be useful to consider the following discussion in CGEL (p. 518–519). That discussion shows that CGEL takes King Arthur to be a proper name with a composite head. It doesn't explicitly treat the question of why King should be taken to be a noun, but will be useful in the discussion that follows, which does.

20.2.2 Proper names with simple and composite heads

The head of a name is the name less the article in the case of weak names.¹ This may be simple, i.e. a single noun (including compounds of various kinds: Fortescue-Smythe, Alsace-Lorraine), or composite, i.e. a nominal with internal syntactic structure.

^{1We distinguish, then, between strong proper names like Kim or New York, where there is no determiner, and weak proper names like the Thames or the Bronx, where definiteness is redundantly marked by the definite article the.}

■ Simple heads

…

■ Composite heads

The main kinds of composite head structures are illustrated in [4]:

[4]   i  ….
       ii  Queen Mary, Pope John Paul, Major White, Nurse Fox, Dr Brown, Mr Black
      iii   …

Appellations

The underlined elements in [4ii] are appellations, pre-head modifiers of personal names, expressing the status of the individual concerned.⁷⁹ The kinds of status they indicate include: royal/aristocratic office or rank (King, Queen, Prince, Earl, Lord, Emperor, Count, etc.); clerical office (Pope, Archbishop, Sister); military and police rank (Private, Captain, Squadron Leader, Admiral, Inspector); political office (President, Senator, Governor, Councillor); judicial office (Judge); academic status (Dr, Professor). The default set of appellations—Mr, Ms, Mrs, Miss, Master—indicate sex and in some cases also marital or maturity status. It is arguable whether appellations form part of the proper name or are an embellishment of it; the case for including them within the name would seem to be stronger in cases like King George or Pope John (where a particular personal name is chosen for use with the appellation on accession to the office) than with others. Some combinations of appellations are permitted: Professor Sir Ernest Rutherford, Her Majesty Queen Elizabeth.

^{79The term 'title' is more commonly used than 'appellation', but we have used 'title' for the proper name of a literary work or comparable artefact, and from a grammatical point of view appellations and titles are quite different.}

Now we can pose the question why, in [4ii] above, do we say that Queen, Pope, Major, Nurse, Dr, and Mr aren't adjectives? After all, functioning as pre-head modifiers of nouns (i.e. attributive modifiers, as in happy people) is very characteristic for adjectives.

The answer consists of several parts.

1. There are other constructions where these same words are clearly nouns. This is especially obvious when they pluralize or take an article or both (e.g. the city of the popes). Of course, this doesn't preclude the possibility that the words in [4ii] are nevertheless adjectives and are merely homonymous with the corresponding nouns.

2. Apart from functioning as pre-head modifiers in constructions such as those in [4ii], these words do not appear in any other constructions that are characteristic of adjectives. In particular: i. None of them are gradable (in Standard English there is no such thing as *more Mr or *very Mr). ii. At least some of them cannot function as predicative complements unless preceded by a determiner (it must be She is a/the/some/my nurse rather than simply *She is nurse). iii. They don't appear postpositively (*Jackie nurse). iv. They never take adverbs as modifiers; we say she is a marvelous nurse, not *she is a marvelously nurse.

3. In general, noun phrases (NPs) are not forbidden from appearing as pre-head modifiers of a noun. Here is a clear example: an Egyptian cotton shirt. Normally, it is clear that this means a shirt made of Egyptian cotton, and so it is clear that Egyptian, an adjective, modifies cotton. Thus, cotton cannot itself be an adjective, but rather must be a noun. While I suppose that it is still just possible to argue that Egyptian cotton, when it appears in front of shirt, has somehow transformed into an 'adjective' or 'adjective phrase'. But this seems hopelessly ad hoc. After all, on that analysis, cotton shirt would have cotton as an adjective, but Egyptian cotton shirt would have cotton as a noun, a constituent of Egyptian cotton; and Egyptian cotton, normally an NP, would in this particular case be transformed into an adjective (phrase?) whose head is the noun cotton—rather than an adjective, as would be expected in an adjective phrase. (And in particular, its head is not the adjective Egyptian.) Given all that, it seems much simpler to allow that nouns (and nominals more generally) can appear as pre-head modifiers of other nouns.

4. Putting it all together: on the one hand, given 1 and 3, there seems to be no reason to think that Queen, Pope, Major, Nurse, Dr, and Mr couldn't be nouns in [4ii]. On the other hand, 2 gives good reasons to doubt that Queen, Pope, Major, Nurse, Dr, and Mr are adjectives. Putting it all together, we conclude that they indeed are nouns in [4ii].

Here is more from CGEL (p. 537) on the subject of attributive modifiers (point 3. above):

(a) Nouns as attributive modifiers

It is important to emphasise that it is not only adjectives that can function as pre-head modifier in the structure of a nominal. A variety of other categories are found in this function (as described in Ch. 5, §14.2), in particular nouns (or nominals):

[27]  a government inquiry             student performance     a London park
         the Clinton administration     the Caroline factor         the biology syllabus
          a computer error

Traditional school grammar (though not scholarly traditional grammar) tends to analyse the underlined nouns here as adjectives - or to say that they are 'nouns used as adjectives'. From our perspective, this latter formulation represents a confusion between categories and functions: they are not nouns used as adjectives, but nouns used as attributive modifiers. Apart from pronouns, just about any noun can appear in this function—including proper nouns, as in the London, Clinton, and Caroline examples. These words can all appear as head of an NP in subject or object function, where they are uncontroversially nouns; to analyse them as adjectives when they are functioning attributively would make the adjective category far too heterogeneous, and require an unwarranted and massive overlap between the adjective and noun categories.⁴

^{4We will not take an attributive modifier to be a noun unless it occurs with the same meaning as head of an NP. In a maiden voyage, for example, maiden does not have the same meaning as in a young maiden from Perth, and will thus be analysed as an adjective even though it has no adjective properties other than that of occurring in attributive function: it cannot be used predicatively or postpositively, and it doesn't admit any dependents.}

^{I do believe CGEL is a bit too pessimistic about maiden not having other properties characteristic of adjectives: it seems that it can be modified by adverbs. In particular, the following are attested in published literature: almost-maiden voyage (here and here); nearly maiden journey (here); nearly maiden blade (here); nearly-maiden speeches (here).}

Attributive nouns fail to qualify as adjectives by virtue of the grading and adverbial dependents criteria. They don't take very or too or the analytic comparative marker more as modifier. More generally, they don't take adverbs as modifier: to the extent that they accept pre-head modifiers, the modifiers are of the same kind as are found modifying nouns functioning as head in NP structure. Compare, for example:

[28]   i  a.  the federal government     b.  a federal government inquiry
         ii  a.  mature students                 b.  mature student performance

Here government and student take the adjectives federal and mature as modifiers, not adverbs: cf. *a federally government inquiry and *maturely student performance. Often the modifier is another noun, as in psychology student performance ("the performance ofstudents of psychology"). This difference in the category of modifiers applies equally in cases where there is homonymy between adjective and noun. Thus a characteristically French response has French as an adjective modified by an adverb, while an Old French dictionary has French as a noun modified by an adjective.

The examples in [27] differ from the simplest type of attributive adjective construction in that there is no matching predicative construction. Compare:

[29]   i  a.  a red jacket                      b.  The jacket is red.
         ii  a.  a government inquiry      b.  *The inquiry is government.

However, nouns denoting the material of which something is composed do show this kind of relationship: compare a cotton sheet and The sheet is cotton. This may appear to make these nouns more adjective-like, but again the modifier test shows that they belong to the noun category, for they are modified by adjectives, not adverbs: a pure cotton sheet and This sheet is pure cotton.

Why is King capitalized?

As far as what gets capitalized and what does not, that is a question of style, and will thus differ from style manual to style manual.

Here are relevant sections from the Chicago Manual of Style (CMOS):

(begin quote)
8: Names, Terms, and Titles of Works

8.19: Titles and offices—the general rule

Civil, military, religious, and professional titles are capitalized when they immediately precede a personal name and are thus used as part of the name (traditionally replacing the title holder’s first name). In formal prose and other generic text, titles are normally lowercased when following a name or used in place of a name (but see 8.20). For abbreviated forms, see 10.11–26.

Abraham Lincoln, president of the United States (or President Abraham Lincoln of the United States); President Lincoln; the president
General Bradley; the general
Cardinal Newman; the cardinal
Governors Ige and Brown; the governors

Although a full name may be used with a capitalized title (e.g., President Abraham Lincoln)—and though it is perfectly correct to do so—some writers choose to avoid using the title before a full name in formal prose, especially with civil, corporate, and academic titles (see 8.22, 8.27, 8.28). (For titles used in apposition to a name, see 8.21.) Note also that once a title has been given, it need not be repeated each time a person’s name is mentioned.

Elizabeth Warren, senator from Massachusetts (or Senator Elizabeth Warren of Massachusetts); Senator Warren; Warren; the senator

8.20: Exceptions to the general rule for titles and offices

In promotional or ceremonial contexts such as a displayed list of donors in the front matter of a book or a list of corporate officers in an annual report, titles are usually capitalized even when following a personal name. Exceptions may also be called for in other contexts for reasons of courtesy or diplomacy.

Maria Martinez, Director of International Sales

A title used alone, in place of a personal name, is capitalized only in such contexts as a toast or a formal introduction, or when used in direct address (see also 6.53, 8.36).

Ladies and Gentlemen, the Prime Minister.
I would have done it, Captain, but the ship was sinking.
Thank you, Mr. President.

8.21: Titles used in apposition

When a title is used in apposition before a personal name—that is, not alone and as part of the name but as an equivalent to it, usually preceded by the or by a modifier—it is considered not a title but rather a descriptive phrase and is therefore lowercased.

the empress Elisabeth of Austria (but Empress Elisabeth of Austria)
German chancellor Angela Merkel (but Chancellor Merkel)
the Argentinian-born pope Francis
former president Carter
former presidents Reagan and Ford
the then secretary of state Hillary Clinton

(end quote)

In contrast, The Associated Press Stylebook recommends capitalizing the title even when used in apposition (e.g. former President Carter, whereas CMOS would have it as former president Carter) :

president Capitalize president only as a formal title before one or more names: President Donald Trump, former Presidents Gerald R. Ford and Jimmy Carter.
     Lowercase in all other uses: The president said Monday he will look into the matter. He is running for president. Lincoln was president during the Civil War.