Coin Change Algorithm - coding challenge
I'll start with a review of your existing code, and then make a suggestion
for a better algorithm.

The first thing to notice is that there are many conversions from arrays
to lists and back to arrays:


In the isPresent() function, the array is converted to a list in order
to check if it contains a given number. But the array is already sorted,
so one can call Arrays.binarySearch instead, which is more also efficient.
The possibleDenominations function “truncates” the given array by conversion
to a list and back to an array.
You could compute the last index to be included instead and then return
a subarray with Arrays.copyOfRange. But I am not sure if this truncating
is needed at all, since your solution algorithm already early returns if 
the values become too large.
In the removeAndReturn function, the array is converted to a list
and back to an array in order to get a new array with the first element
removed.


All these conversions can be avoided completely: Either


keep the original array and pass indices (of the first and last
entry to be considered) around, or
store the values in an (Array)List right at the beginning, and use 
list.subList() to pass views of a portion of the list around, without
actually copying the elements.


The method


public static boolean isPossible(int toMake, int sum, Integer[] arr) {



can be simplified by taking a single parameter targetSum instead of
toMake and sum:

public static boolean isPossible(int targetSum, Integer[] arr) {
    if (targetSum == 0) {
        return true;
    } else if (targetSum &lt; 0) {
        return false;
    }
    for (int num : arr) {
        if (isPossible(targetSum - num, removeAndReturn(num, arr))) {
            return true;
        }
    }
    return false;
}


Further remarks:


“Test” is a non-descriptive name for a program. Why not name it after the
challenge, for example public class CoinChange? 
Why do you call nextByte() if the result is assigned to an int?
The variable name coins does not clearly indicate that this is the
number of coins.
coinsDenominationarray is an array, but there is no need to make the type
part of the variable name, I would call it for example coinDenominations or
coinValues.
Most of the code is done in a separate function, which is good. I would put
the calculation of maxPossible and the sorting into that function as well,
so that I/O and the actual computation are separated completely.
The parameter name arr in the solve function  is non-descriptive.
Why not use the same name as in the main program?
All methods (with the only exception of main) can be private.


Putting it all together, the program could look like this:

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.Collections;

public class CoinChange {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int numCoins = scan.nextInt();

        ArrayList&lt;Integer&gt; coinValues = new ArrayList&lt;Integer&gt;();
        for (int i = 0; i &lt; numCoins; i++) {
            coinValues.add(scan.nextInt());
        }
        int firstNotPossible = findFirstNotPossible(coinValues);
        System.out.println(firstNotPossible);
    }

    private static int findFirstNotPossible(List&lt;Integer&gt; coinValues) {
        Collections.sort(coinValues);

        // Compute sum of values plus one:
        int maxNotPossible = 1;
        for (int value : coinValues) {
            maxNotPossible += value;
        }

        for (int num = 1; num &lt; maxNotPossible; num++) {
            if (!coinValues.contains(num) &amp;&amp; !isSummable(num, coinValues)) {
                return num;
            }
        }
        return maxNotPossible;
    }

    // Check if `targetSum` is representable as a sum of numbers in `values`
    // (which is assumed to be a sorted list of positive numbers).
    private static boolean isSummable(int targetSum, List&lt;Integer&gt; values) {
        if (targetSum == 0) {
            return true;
        } else if (targetSum &lt; 0) {
            return false;
        }
        for (int i = 0; i &lt; values.size(); i += 1) {
            if (isSummable(targetSum - values.get(i), values.subList(i + 1, values.size()))) {
                return true;
            }
        }
        return false;
    }
}


A better algorithm

Your isPossible() function solves the "Subset sum problem"
with “brute force,” i.e. by (recursively) trying all possible combinations.

This problem can be efficiently solved with "dynamic programming", as described in
the Wikipedia article.

But this problem can be solved even simpler: 


A number \$ N \$  stores the lowest value which is not
representable as sum of coin values considered so far, initially \$ N = 1 \$.
For all values \$ v \$ in the (sorted) array of coin values:


If \$ v &gt; N \$ then we are done, \$ N \$ is not representable.
Otherwise \$ N \$ is incremented by \$ v \$.



This requires only a single traversal of the array, and no additional storage:

import java.util.Scanner;
import java.util.Arrays;

public class CoinChange {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int numCoins = scan.nextInt();

        int[] coinValues = new int[numCoins];
        for (int i = 0; i &lt; numCoins; i++) {
            coinValues[i] = scan.nextInt();
        }
        int firstNotPossible = findFirstNotPossible(coinValues);
        System.out.println(firstNotPossible);
    }

    private static int findFirstNotPossible(int[] coinValues) {
        Arrays.sort(coinValues);

        int firstNotPossible = 1;
        for (Integer value : coinValues) {
            if (value &gt; firstNotPossible) {
                break;
            }
            firstNotPossible += value; 
        }
        return firstNotPossible;
    }
}