You'll need two algorithms (definitions, actually) here:
- one to define a distance between answers with in questions
- one to define a distance between complete questionnaires
It makes working with 2 easier if you choose 1 such that they are all compatible, or normalized. (For example, you can assign a distance of 1 to total disagreement like in "Nope" vs "Yes" and a distance 0.5 for "Maybe" and anything not-maybe. If you then have questions like "rate on a scale from 1 to 10", a ratings 1 vs 10 would have a distance of 1, whereas 4 vs 5 would have a distance of 1/9. Identical answers always have a distance of 0).
Then, you can define a distance between questionnaires; most easily by adding them up (which gives you the "Taxicab distance"), and possibly normalizing to a range from 0 to 1 again by dividing by the number of questions.
If you want to express these distances in terms of similarity, you can just subtract them from 1 and multiply by 100%. That does have the effect that identical answers are "100% similar", but only completely opposite answers are "0% similar". (I.e. you will probably never see "0% similar" in practice). This is to be expected, however, considering there is "99% similarity" between the human and chimpanzee genome, or "70%" between human and fish.
What you make of that will depend on your use case. If you can expect your users to understand what these values mean you can use them as they are; if you want just a quick and easily understood score (like in those online "How much of an X are you?" tests), it may make sense to just stretch the scale and clip to 0%. (I.e. take the distance $d$, calculate $sim = (1 - 3 \times d) \times 100%$ and show any negative values as "0% match", where the factor 3 depends on the size of your questionnaire and the diversity of the answers). That won't be a highly scientific metric, but then again, "percent match" often are not.